C語言數(shù)據(jù)結(jié)構(gòu)系列篇二叉樹的概念及滿二叉樹與完全二叉樹
?? 鏈接：C語言數(shù)據(jù)結(jié)構(gòu)系列之樹的概念結(jié)構(gòu)和常見表示方法
0x00 概念
?? 定義：二叉樹既然叫二叉樹，顧名思義即度最大為2的樹稱為二叉樹。 它的度可以為 1 也可以為 0，但是度最大為 2 。
?? 一顆二叉樹是節(jié)點的一個有限集合，該集合：
① 由一個根節(jié)點加上兩顆被稱為左子樹和右子樹的二叉樹組成
② 或者為空
?? 觀察上圖我們可以得出如下結(jié)論：
① 二叉樹不存在度大于 2 的節(jié)點，換言之二叉樹最多也只能有兩個孩子。
② 二叉樹的子樹有左右之分，分別為左孩子和右孩子。次序不可顛倒，因此二叉樹是有序樹。
?? 注意：對于任意的二叉樹都是由以下幾種情況復合而成的：
0x01 滿二叉樹
?? 定義：一個二叉樹，如果每一層的節(jié)點數(shù)都達到了最大值（均為2），則這個二叉樹就可以被稱作為 "滿二叉樹" 。
?? 換言之，如果一個二叉樹的層數(shù)為，且節(jié)點總數(shù)是
，則他就是一個滿二叉樹。
?? 計算公式：
① 已知層數(shù)求總數(shù)：
② 已知總數(shù)求層數(shù)：
? 十億個節(jié)點，滿二叉樹是多少層？
?? ≈ 10億多
0x02 完全二叉樹
?? 定義：對于深度為 的，有
個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為
的滿二叉樹中編號從 1 至
的結(jié)點一一對應時稱之為完全二叉樹。
?? 前 層是滿的，最后一層不滿，但是最后一層從左到右是連續(xù)的。
完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。所以，滿二叉樹是一種特殊的完全二叉樹（每一層節(jié)點均為2）。
?? 常識：
① 完全二叉樹中，度為 1 的最多只有 1 個。
② 高度為 的完全二叉樹節(jié)點范圍是
0x03 二叉樹的性質(zhì)
?? 四點規(guī)則：
① 若規(guī)定根節(jié)點的層數(shù)為 1 ，則一顆非空二叉樹的第 層上最多有
個節(jié)點。
② 若規(guī)定根節(jié)點的層數(shù)為 1 ，則深度為 的二叉樹最大節(jié)點數(shù)是
.
③ 對任何一顆二叉樹，如果度為 0 其葉子結(jié)點個數(shù)為 ，度為 2 的分支節(jié)點個數(shù)為
，則有
。換言之，度為 0 的永遠比度為 2 的多一個葉子結(jié)點。
④ 若規(guī)定根節(jié)點的層數(shù)為 1 ， 具有 個節(jié)點的滿二叉樹的深度
（log是以2為底，n+1的對數(shù)）。
?? 對于有 個節(jié)點的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點從 0 開始編號，則對于序號為
的節(jié)點有：
（非完全二叉樹，也可以用數(shù)組存放，但會浪費很多空間）
假設 是父節(jié)點在數(shù)組中的下標，此公式僅適用于完全二叉樹：
① 求左孩子：
② 求右孩子：
③ 求父親（假設不關注是左孩子還是右孩子）：
④ 判斷是否有左孩子：
⑤ 判斷是否由右孩子：
?? PS：二叉樹不一定要標準，比如這個其實也是二叉樹：
課后練習：
1. 某二叉樹共有 399 個結(jié)點，其中有 199 個度為 2 的結(jié)點，則該二叉樹中的葉子結(jié)點數(shù)為（ ）
A. 不存在這樣的二叉樹
B. 200
C. 198
D. 199
2. 在具有 2n 個結(jié)點的完全二叉樹中，葉子結(jié)點個數(shù)為（ ）
A. n
B. n+1
C. n-1
D. n/2
3. 一棵完全二叉樹的節(jié)點數(shù)位為531個，那么這棵樹的高度為（ ）
A. 11
B. 10
C. 8
D. 12
5. 一個具有767個節(jié)點的完全二叉樹，其葉子節(jié)點個數(shù)為（）
A. 383
B. 384
C. 385
D. 386
參考資料：
Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .
百度百科[EB/OL]. []. https://baike.baidu.com/.
?? 筆者：王亦優(yōu)
?? 更新： 2021.11.24
? 勘誤： 無
?? 聲明： 由于作者水平有限，本文有錯誤和不準確之處在所難免，本人也很想知道這些錯誤，懇望讀者批評指正！
本篇完。
到此這篇關于C語言數(shù)據(jù)結(jié)構(gòu)系列篇二叉樹的概念及滿二叉樹與完全二叉樹的文章就介紹到這了,更多相關C語言 二叉樹的概念內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
本文主要介紹C語言 字符串指針,這里整理了詳細資料，并附示例代碼及實現(xiàn)結(jié)果，有興趣的小伙伴可以參考下2016-08-08
C++ Cartographer源碼中關于Sensor的數(shù)據(jù)走向深扒
這篇文章主要介紹了C++ Cartographer源碼中關于Sensor的數(shù)據(jù)走向，整個Cartographer源碼閱讀是很枯燥的, 但絕對是可以學到東西的，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習吧2023-03-03
想突破C語言的學習，對指針的掌握是非常重要的，本文為大家總結(jié)了C語言中指針的相關知識點，文中的示例代碼講解詳細，感興趣的小伙伴可以學習一下2022-10-10
下面小編就為大家?guī)硪黄Ｓ肏ash算法(C語言的簡單實現(xiàn))。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-09-09
這篇文章主要為大家詳細介紹了Qt實現(xiàn)TCP客戶端和服務器通訊程序，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
這篇文章主要介紹了opencv實現(xiàn)三幀差法的相關資料，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03
這篇文章主要為大家詳細介紹了C語言模擬實現(xiàn)學生學籍管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-07-07
這篇文章主要介紹了CC和C++變量類型及內(nèi)存大小,是C++入門學習中的基礎知識,需要的朋友可以參考下，希望能夠給你帶來幫助2021-09-09
在C語言中，字符(character)這個術(shù)語具有兩個層次上的含義：書寫源程序的字符和程序處理的字符2013-10-10
這篇文章主要為大家詳細介紹了OpenCV實現(xiàn)直線檢測并消除，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-06-06