您好,登錄后才能下訂單哦!
這篇文章主要介紹C++中數(shù)據(jù)結(jié)構(gòu)完全二叉樹的判斷分析,文中介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們一定要看完!
C++ 數(shù)據(jù)結(jié)構(gòu)完全二叉樹的判斷
完全二叉樹(Complete Binary Tree):若設(shè)二叉樹的深度為h,除第h層外,其他各層(1~h-1)的節(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù),第h層所有的節(jié)點(diǎn)都連續(xù)集中在最左邊,這就是完全二叉樹。完全二叉樹由滿二叉樹而引起來的。對于深度為K的,有n個(gè)節(jié)點(diǎn)的二叉樹,當(dāng)且僅當(dāng)每一個(gè)節(jié)點(diǎn)都與深度為K的滿二叉樹中編號從1到n的節(jié)點(diǎn)一一對應(yīng)時(shí)稱之為完全二叉樹。
注意:滿二叉樹一定是完全二叉樹,但完全二叉樹不一定是滿二叉樹。
完全二叉樹的特點(diǎn):完全二叉樹的效率極高,堆是一種完全二叉樹或者近似完全二叉樹,像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能優(yōu)化。
判斷完全二叉樹的方法:從上圖我們可以看出,完全二叉樹可能會出現(xiàn)以下情況:左子樹存在,右子樹不存在;左子樹存在,有字?jǐn)?shù)存在;左、右子樹都不存在;所以我們可以利用廣度優(yōu)先遍歷(層序遍歷)將二叉樹進(jìn)行遍歷,設(shè)置一個(gè)標(biāo)志位,當(dāng)遇到一個(gè)空節(jié)點(diǎn)時(shí),將標(biāo)志位為修改;當(dāng)后面在遇到有效節(jié)點(diǎn)并且標(biāo)志位被修改時(shí),則該二叉樹不是完全二叉樹。
當(dāng)該二叉樹為空時(shí)、修改標(biāo)志位后無有效節(jié)點(diǎn)時(shí),該二叉樹為完全二叉樹。
代碼實(shí)現(xiàn):
#include<iostream> using namespace std; #include<queue> template<class T> struct TreeNode //二叉樹結(jié)點(diǎn) { 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; //設(shè)置標(biāo)志位 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; //修改標(biāo)志位 } return true; } return true; }
以上是“C++中數(shù)據(jù)結(jié)構(gòu)完全二叉樹的判斷分析”這篇文章的所有內(nèi)容,感謝各位的閱讀!希望分享的內(nèi)容對大家有幫助,更多相關(guān)知識,歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。