C++ 數據結構完全二叉樹的判斷
完全二叉樹（Complete Binary Tree）：若設二叉樹的深度為h,除第h層外，其他各層（1~h-1）的節點數都達到最大個數，第h層所有的節點都連續集中在最左邊，這就是完全二叉樹。完全二叉樹由滿二叉樹而引起來的。對于深度為K的，有n個節點的二叉樹，當且僅當每一個節點都與深度為K的滿二叉樹中編號從1到n的節點一一對應時稱之為完全二叉樹。
注意：滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹。
完全二叉樹的特點：完全二叉樹的效率極高，堆是一種完全二叉樹或者近似完全二叉樹，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能優化。
判斷完全二叉樹的方法：從上圖我們可以看出，完全二叉樹可能會出現以下情況：左子樹存在，右子樹不存在；左子樹存在，有字數存在；左、右子樹都不存在；所以我們可以利用廣度優先遍歷（層序遍歷）將二叉樹進行遍歷，設置一個標志位，當遇到一個空節點時，將標志位為修改；當后面在遇到有效節點并且標志位被修改時，則該二叉樹不是完全二叉樹。
當該二叉樹為空時、修改標志位后無有效節點時，該二叉樹為完全二叉樹。
代碼實現：
#include<iostream> using namespace std; #include<queue> template<class T> struct TreeNode //二叉樹結點 { T _value; TreeNode<T>* _left; TreeNode<T>* _right; TreeNode(const T& value) :_value(value) , _left(NULL) , _right(NULL) {} }; template<class T> bool Is_completeTree(TreeNode<T>* node) { queue<TreeNode<T>*> q; if (node != NULL) { q.push(node); TreeNode<T>* cur = NULL; bool flag = false; //設置標志位 while (!q.empty()) { cur = q.front(); q.pop(); if (cur) { if (flag) return false; q.push(cur->_left); q.push(cur->_right); } else flag = true; //修改標志位 } return true; } return true; } 感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
新聞熱點
疑難解答
圖片精選
