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é)點，換言之二叉樹最多也只能有兩個孩子。
② 二叉樹的子樹有左右之分，分別為左孩子和右孩子。次序不可顛倒，因此二叉樹是有序樹。
?? 注意：對于任意的二叉樹都是由以下幾種情況復(fù)合而成的：
0x01 滿二叉樹
?? 定義：一個二叉樹，如果每一層的節(jié)點數(shù)都達(dá)到了最大值（均為2），則這個二叉樹就可以被稱作為 "滿二叉樹" 。
?? 換言之，如果一個二叉樹的層數(shù)為，且節(jié)點總數(shù)是
，則他就是一個滿二叉樹。
?? 計算公式：
① 已知層數(shù)求總數(shù)：
② 已知總數(shù)求層數(shù)：
? 十億個節(jié)點，滿二叉樹是多少層？
?? ≈ 10億多
0x02 完全二叉樹
?? 定義：對于深度為 的，有
個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為
的滿二叉樹中編號從 1 至
的結(jié)點一一對應(yīng)時稱之為完全二叉樹。
?? 前 層是滿的，最后一層不滿，但是最后一層從左到右是連續(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 的永遠(yuǎn)比度為 2 的多一個葉子結(jié)點。
④ 若規(guī)定根節(jié)點的層數(shù)為 1 ， 具有 個節(jié)點的滿二叉樹的深度
（log是以2為底，n+1的對數(shù)）。
?? 對于有 個節(jié)點的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點從 0 開始編號，則對于序號為
的節(jié)點有：
（非完全二叉樹，也可以用數(shù)組存放，但會浪費很多空間）
假設(shè) 是父節(jié)點在數(shù)組中的下標(biāo)，此公式僅適用于完全二叉樹：
① 求左孩子：
② 求右孩子：
③ 求父親（假設(shè)不關(guān)注是左孩子還是右孩子）：
④ 判斷是否有左孩子：
⑤ 判斷是否由右孩子：
?? PS：二叉樹不一定要標(biāo)準(zhǔn)，比如這個其實也是二叉樹：
課后練習(xí)：
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
? 勘誤： 無
?? 聲明： 由于作者水平有限，本文有錯誤和不準(zhǔn)確之處在所難免，本人也很想知道這些錯誤，懇望讀者批評指正！
本篇完。
到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)系列篇二叉樹的概念及滿二叉樹與完全二叉樹的文章就介紹到這了,更多相關(guān)C語言 二叉樹的概念內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了用C語言求解一元二次方程的簡單實現(xiàn)方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
這篇文章主要介紹了C++語言中的二元運算符和賦值運算符,文中列出了可重載的運算符列表,需要的朋友可以參考下2016-01-01
Opencv學(xué)習(xí)教程之漫水填充算法實例詳解
這篇文章主要給大家介紹了Opencv學(xué)習(xí)教程之漫水填充算法的相關(guān)資料，文中給出了詳細(xì)的示例代碼供大家參考學(xué)習(xí)，對大家具有一定的參考價值，需要的朋友們下面跟著小編一起來學(xué)習(xí)學(xué)習(xí)吧。2017-06-06
C語言結(jié)構(gòu)體(struct)的詳細(xì)講解
C語言中,結(jié)構(gòu)體類型屬于一種構(gòu)造類型(其他的構(gòu)造類型還有：數(shù)組類型,聯(lián)合類型),下面這篇文章主要給大家介紹了關(guān)于C語言結(jié)構(gòu)體(struct)的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-03-03
本文主要介紹了C++11各種鎖的具體使用，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
詳解C++編程中向函數(shù)傳遞引用參數(shù)的用法
這篇文章主要介紹了詳解C++編程中向函數(shù)傳遞引用參數(shù)的用法,包括使函數(shù)返回引用類型以及對指針的引用,需要的朋友可以參考下2016-01-01
本文主要介紹了多維數(shù)組在C++語言中的定義、初始化、下標(biāo)引用以及使用范圍for語句處理多維數(shù)組的方法,具有一定的參考價值,感興趣的可以了解一下2025-02-02
C++11新特性之右值引用與完美轉(zhuǎn)發(fā)詳解
C++11標(biāo)準(zhǔn)為C++引入右值引用語法的同時，還解決了一個短板，即使用簡單的方式即可在函數(shù)模板中實現(xiàn)參數(shù)的完美轉(zhuǎn)發(fā)。本文就來講講二者的應(yīng)用，需要的可以參考一下2022-09-09
這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)簡易通訊錄功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-06-06
今天小編就為大家分享一篇c語言 字符串的拼接和分割實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12