?? 鏈接：C語言數(shù)據(jù)結(jié)構(gòu)系列之樹的概念結(jié)構(gòu)和常見表示方法

0x00 概念

?? 定義：二叉樹既然叫二叉樹，顧名思義即度最大為2的樹稱為二叉樹。 它的度可以為 1 也可以為 0，但是度最大為 2 。 

?? 一顆二叉樹是節(jié)點的一個有限集合，該集合：

     ① 由一個根節(jié)點加上兩顆被稱為左子樹和右子樹的二叉樹組成     

     ② 或者為空

?? 觀察上圖我們可以得出如下結(jié)論：

     ① 二叉樹不存在度大于 2 的節(jié)點，換言之二叉樹最多也只能有兩個孩子。

     ② 二叉樹的子樹有左右之分，分別為左孩子和右孩子。次序不可顛倒，因此二叉樹是有序樹。

?? 注意：對于任意的二叉樹都是由以下幾種情況復(fù)合而成的：

0x01 滿二叉樹

?? 定義：一個二叉樹，如果每一層的節(jié)點數(shù)都達到了最大值（均為2），則這個二叉樹就可以被稱作為 "滿二叉樹" 。

?? 換言之，如果一個二叉樹的層數(shù)為，且節(jié)點總數(shù)是 ，則他就是一個滿二叉樹。

?? 計算公式：

 ① 已知層數(shù)求總數(shù)：

 ② 已知總數(shù)求層數(shù)： 

? 十億個節(jié)點，滿二叉樹是多少層？

?? ≈ 10億多

0x02 完全二叉樹

?? 定義：對于深度為 的，有個結(jié)點的二叉樹，當且僅當其每一個結(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 的永遠比度為 2 的多一個葉子結(jié)點。

 ④ 若規(guī)定根節(jié)點的層數(shù)為 1 ， 具有  個節(jié)點的滿二叉樹的深度     （log是以2為底，n+1的對數(shù)）。

?? 對于有  個節(jié)點的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點從 0 開始編號，則對于序號為  的節(jié)點有：

（非完全二叉樹，也可以用數(shù)組存放，但會浪費很多空間）

假設(shè)  是父節(jié)點在數(shù)組中的下標，此公式僅適用于完全二叉樹：

① 求左孩子： 

② 求右孩子：

③ 求父親（假設(shè)不關(guān)注是左孩子還是右孩子）： 

④  判斷是否有左孩子：

⑤  判斷是否由右孩子：

 ?? PS：二叉樹不一定要標準，比如這個其實也是二叉樹：

課后練習(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

? 勘誤： 無

?? 聲明： 由于作者水平有限，本文有錯誤和不準確之處在所難免，本人也很想知道這些錯誤，懇望讀者批評指正！

本篇完。

到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)系列篇二叉樹的概念及滿二叉樹與完全二叉樹的文章就介紹到這了,更多相關(guān)C語言 二叉樹的概念內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！