滿二叉樹一定是二叉樹嗎

原創： 老表 簡說Python

今日問題

“”“介紹二叉樹的基礎知識目錄1> 什麼是二叉樹？2> 二叉樹結點的屬性 2。1>結點的度 2。2>葉子結點 2。3>分支結點 2。4>左孩子、右孩子、雙親結點 2。5>路徑、路徑長度 2。6>祖先、子孫 2。7>結點的層數3> 樹的屬性 3。1>樹的深度 3。1>樹的度4> 什麼是滿二叉樹？5> 什麼是完全二叉樹？6> 二叉樹的基本性質7> 實戰”“”

1> 什麼是二叉樹？

二叉樹（Binary Tree），他是n（n>=0）個有限元素的集合，該集合或者為空（n=0）， 或者有一個稱為根（root）的元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹 組成，當集合為空（n=0）時，稱為空二叉樹。

2> 二叉樹結點的屬性

2.1>結點的度

結點所擁有的子樹的個數稱為該結點的度。葉子結點的度為0。

2.2>葉子結點

度為0的結點稱為葉子結點。

2.3>分支結點

度不為0的結點稱為分支結點，或稱為非終端結點，一棵樹除了葉子結點，其他的 結點都是分支結點。

2.4>左孩子、右孩子、雙親結點

一個結點的子樹的根結點稱為該結點的孩子，該結點稱為雙親結點，該結點的左子 樹的根結點稱為該結點的左孩子，該結點的右子樹的根結點稱為該結點的右孩子。

2.5>路徑、路徑長度

如果一顆樹的一串結點n1，n2，n3。。。nk，有如下關係，結點ni是n（i+1）的雙親結點 （1<=i

2.6>祖先、子孫

在樹中，如果有一條路徑從結點M到結點N，那麼結點M稱為結點N的祖先，而結點N稱 為結點M的子孫。

2.7>結點的層數

規定根結點的層數為1，其餘結點層數等與其雙親結點的層數加1。

3> 樹的屬性

3.1>樹的深度

樹中所有結點的最大層數稱為樹的深度。

3.1>樹的度

樹中各結點的度的最大值稱為該樹的度。

4> 什麼是滿二叉樹？

在一顆二叉樹中，如果所有的分支結點都有左子樹和右子樹，並且所有葉子結點都在同一層，這樣的 一顆二叉樹稱為滿二叉樹。如下所示：

A / \ B C

5> 什麼是完全二叉樹？

一顆深度為k的有n個結點的二叉樹，對樹中的結點按從上到下，從左到右的順序進行編號，如果編號為i（1<=i<=n） 的結點與滿二叉樹中編號為i的結點在二叉樹中的位置相同，則該樹為完全二叉樹。

特點：完全二叉樹的葉子結點只能出現在最下層和最次層，而且最下層葉子結點集中在左邊。

滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。如下圖所示：

A / \ B C / \ E F

6> 二叉樹的基本性質

6.1> 一顆非空二叉樹的第i層上最多有2^(i-1)個結點（i>=1）。

證明：

一個結點最多有兩個子樹，故 第1層1個結點（2^（1-1））， 第2層最多2個結點（2^（2-1））， 第3層最多4個結點（2^（3-1）） 依次類推：第i層最多有2^（i-1）個結點。

6.2> 一顆深度為k的二叉樹中，最多有2^k - 1個結點，最少有k個結點。

證明：

由6。1，可知一顆深度為k的二叉樹最多的結點樹S = 2^0 + 2^1 + 2^2 + 。。。 + 2^k 由等比數列計算前n項和公式可以計算出：S = 2^k - 1 每一層至少有一個結點，故深度為k的二叉樹最少有k個結點。

6.3> 對於一顆非空二叉樹，度為0的結點（即葉子結點）總是比度為2的結點多一個，如果葉子結點個數為n0，度數為2的結點為n2，則有 n0 = n2 + 1。

證明：

假設度數為1的結點數為n1，則二叉樹的結點總數S = n0 + n1 + n2，再根據結點度數的性質，度數為 0的結點沒有子結點，度數為1的結點有一個子結點，度數為2的結點有兩個子結點，所以二叉樹的結點總數還可 以表示為S = n00 + n11 + n22 +1 = n1 + 2n2 + 1，所以n0 + n1 + n2 = n1 + 2*n2 + 1，整理 得：n0 = n2 + 1。

6.4>具有n個結點的完全二叉樹的深度為「log2 n」 + 1

證明：

假設該完全二叉樹的深度為k，則該完全二叉樹的總結點數應該是在深度為k和深度為k-1的滿二叉樹之間， 深度為k-1的滿二叉樹結點總數為：2^（k-1） - 1，想要變成深度為k的完全二叉樹，則至少在原二叉樹基礎上 加一個結點，故深度為k的完全二叉樹的結點總數 n >= 2^（k-1） - 1 + 1 即： 2^（k-1） <= n <= 2^k - 1 < 2^k 解得：log2 n <= k < log2 n + 1 由於k為整數，故 k = 「log2 （n+1）」 + 1 注：「」 表示向下取整，如：「3。5」 = 3

6.5> 對於具有n個結點的完全二叉樹，如果按照從上到下，從左到右的順序對二叉樹中的所有結點從1開始順序編號，則對任意的序號為i的結點有：

（1）如果i > 1，則序號為i的結點的雙親結點的編號為i/2（/ 表示取商的整數部分）；如果i = 1，則序號為i 的結點為根結點，無雙親結點。

（2）如果 2i <= n，則序號為i的結點的左孩子結點的序號為2i；如果2i > n，則序號為i的結點無左孩子。

（3）如果 2i+1 <= n，則序號為i的結點的右孩子結點的序號為2i+1；如果2i+1 > n，則序號為i的結點無右孩子。

注：若從0開始編號，則對應的i號結點的雙親結點的編號為：（i-1）/2；左孩子的編號為：2i+1，右孩子的編號為：2i+2。

7> 實戰

S：表示二叉樹的結點總數n0：表示葉子結點個數n1：表示度數為1的結點個數n2：表示度數為2的結點個數

>7.1 一顆完全二叉樹上有1001個結點，求葉子結點的個數？

解：S = n1 + 2*n2 + 1在完全二叉樹中度數為1的結點個數最多為1，最少為0（滿二叉樹）當n1 = 1 時，有：1001 = 1 + 2*n2 + 1 解得：n2 = 999/2，不滿足題意，舍；當n1 = 0 時，有：1001 = 0 + 2*n2 + 1 解得：n2 = 500，又n0 = n1 + 1 ， ——- 性質3故 n0 = 501，即葉子結點個數為501。

>7.2 如果根的層次為1，具有61個結點的完全二叉樹的高度為多少？

解：這裡的高度也就是深度，由完全二叉樹的深度 k = 「log2 n」 + 1 得 ——- 性質4該完全二叉樹的高度為：「log2 61」 + 1 = 6。

>7.3 在具有100個結點的二叉樹中，其邊的數目是多少？

解：在二叉樹中，除開根結點，每個結點都有一條入邊，故100個結點的二叉樹中有99條邊。

>7.4 寫出下面這顆樹的基本屬性值：

A / \ B C / \ / \ D E F G / \ H I這是一顆完全二叉樹結點總數：9度數為0的（葉子）結點數：5度數為1的結點數：0度數為2的結點數：4樹的深度：假設根結點為第一層，則樹的深度為 4樹的度：2結點B的雙親結點：A結點B的左孩子：D結點B的右孩子：E結點D的祖先：A從結點A到結點H為一條路徑，路徑長度為：3

本文程式碼思路來自書籍《Python程式設計師面試寶典》，書中部分程式碼有問題，文中已經修改過了，並新增上了豐厚的註釋，方便大家學習。

最後，我自己是一名從事了多年開發的Python老程式設計師，辭職目前在做自己的Python私人定製課程，今年年初我花了一個月整理了一份最適合2019年學習的Python學習乾貨，可以送給每一位喜歡Python的小夥伴，想要獲取的可以關注我的頭條號並在後臺私信我：01，即可免費獲取。