C++ 數(shù)據(jù)結(jié)構(gòu)完全二叉樹的判斷
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)化。
判斷完全二叉樹的方法：從上圖我們可以看出，完全二叉樹可能會(huì)出現(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;
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
相關(guān)文章
這篇文章主要介紹了C++函數(shù)的默認(rèn)參數(shù)得相關(guān)資料,C++中的默認(rèn)參數(shù)的用法和Python基本一致。使用默認(rèn)參數(shù)的方法非常簡單，也就是我們在函數(shù)聲明的時(shí)候，就為某些參數(shù)指定好默認(rèn)值,當(dāng)我們調(diào)用函數(shù)的時(shí)候,如果沒有傳入對應(yīng)的參數(shù),那么則使用默認(rèn)值，下面來看文章具體內(nèi)容吧2021-11-11
這篇文章主要介紹了C++操作SQLite簡明教程,包含創(chuàng)建表、插入數(shù)據(jù)、查詢數(shù)據(jù)等常用操作,需要的朋友可以參考下2014-06-06
這篇文章主要介紹了C++如何獲取鼠標(biāo)點(diǎn)擊位置問題,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-08-08
這篇文章主要介紹了貪吃蛇游戲C++命令行版實(shí)例代碼,包含了常見的循環(huán)語句及相關(guān)游戲規(guī)則的判定方法,有助于更好的理解游戲設(shè)計(jì)原理,需要的朋友可以參考下2014-09-09
這篇文章主要為大家詳細(xì)介紹了基于C語言代碼實(shí)現(xiàn)掃雷游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-11-11
元組tuple是C++的一個(gè)模板，不同tuple類型的成員類型也不相同，但是一個(gè)tuple可以有任意數(shù)量的成員，今天通過本文給大家介紹C++元組tuple類型，感興趣的朋友一起看看吧2022-06-06
這篇文章主要介紹了VC判斷一個(gè)文件為目錄的方法,在Windows應(yīng)用程序設(shè)計(jì)中非常具有實(shí)用價(jià)值,需要的朋友可以參考下2014-10-10
C語言中數(shù)據(jù)結(jié)構(gòu)之鏈表歸并排序?qū)嵗a
這篇文章主要介紹了C語言中數(shù)據(jù)結(jié)構(gòu)之鏈表歸并排序?qū)嵗a的相關(guān)資料,需要的朋友可以參考下2017-05-05
通過頭文件的形式直接調(diào)用自定義的函數(shù)，從而免去對函數(shù)的原型進(jìn)行聲明，本文就詳細(xì)的介紹一下VS2019中在源文件中如何使用自己寫的頭文件，感興趣的可以了解一下2021-09-09
C語言中for循環(huán)問題（一個(gè)小坑需注意）
這篇文章主要給大家介紹了關(guān)于C語言中for循環(huán)問題的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03