樹的概念及結構
樹的概念
?樹是一種非線性的資料結構，它是由n(n>=0)個有限結點組成的一個具有層次關系的集合，把它叫做“樹”，是因為它看起來像一顆倒掛的樹，也就是說它是根朝上，而葉朝下的，
樹的特點：
?有一個特殊的結點，稱為根結點，根結點沒有前驅結點，
?除根結點外，其余結點被分成M(M>0)互不相交的集合T1,T2…Tm，其中每一個集合Ti(1<=i<=m)又是一顆結構與樹類似的子樹，
?每棵子樹的根結點有且僅有一個前驅，可以有0個或多個后繼，
?因此，樹是遞回定義的，
樹中的專有名詞
?結點的度：一個結點含有的子樹的個數稱為該結點的度，
?葉結點（終端結點）：度為0的結點稱為葉結點，
?非終端結點（分支結點）：度不為0的結點，
?父結點（雙親結點）：若一個結點含有子結點，則這個結點稱為其子結點的父結點，
?子結點（孩子結點）：一個結點含有的子樹的根結點稱為該結點的子結點，
?兄弟結點：具有相同父結點的結點互稱為兄弟結點，
?樹的度：一棵樹中，最大的結點的度稱為樹的度，
?結點的層次：從根開始定義起，根為第一層，根的子結點為第二層，以此類推，
?樹的高度（樹的深度）：樹中結點的最大層次，
?堂兄弟結點：雙親在同一層的結點互稱為堂兄弟結點，
?結點的祖先：從根到該結點所經分支上的所有結點，
?子孫：以某結點為根的子樹中任一結點都稱為該結點的子孫，
?森林：由m(m>0)棵互不相交的樹組成的集合稱為森林，
樹的表示
?樹結構相對于線性表就比較復雜了，要存盤和表示起來就比較麻煩了，實際中樹有很多種表示方法，如：雙親表示法、孩子表示法、孩子兄弟表示法等等，其中最常用的是孩子兄弟表示法，
?孩子兄弟表示法中，所定義的結點型別大致是這樣的：
typedef int DataType
struct Node
{
struct Node* firstChild; //第一個孩子結點
struct Node* nextBrother; //指向下一個兄弟結點
DataType data; //結點中的資料域
};
對于任意樹，我們都可以用孩子兄弟法訪問到樹中的每一個結點：
樹在實際中的運用（表示檔案系統的目錄樹結構）
二叉樹的概念及其重要性質
二叉樹的概念
?二叉樹是n個結點的有限集合，該集合或者為空，或者是由一個根結點加上兩棵分別稱為左子樹和右子樹的二叉樹組成，當集合為空時，稱該二叉樹為空二叉樹，
二叉樹的特點：
?每個結點最多有兩個棵子樹，即二叉樹不存在度大于2的結點，
?二叉樹的子樹有左右之分，其子樹的次序不能顛倒，
自然界中的二叉樹
資料結構中的二叉樹
特殊的二叉樹
?滿二叉樹：一個二叉樹，如果每一層的結點數都達到最大值，則這個二叉樹就是滿二叉樹，也就是說，如果一個二叉樹的層數為k，且結點總數是2k-1，則它就是滿二叉樹，
?完全二叉樹：完全二叉樹是效率很高的資料結構，完全二叉樹是由滿二叉樹而引出來的，對于深度為K，有N個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至N的結點一一對應時稱之為完全二叉樹，要注意的是滿二叉樹是一種特殊的完全二叉樹，
總結：
?滿二叉樹：若樹的深度為K，那么它的每一層的結點數必須都是滿的，
?完全二叉樹：若數的深度為K，那么它的前K-1層的結點數必須都是滿的，第K層的結點數可以不是滿的但是從左到右必須是連續的，
二叉樹的性質（重要！！！）
?性質一：若規定根結點的層數為1，則一棵非空二叉樹的第i層上最多有2i-1個結點，
?性質二：若規定根結點的層數為1，則深度為h的二叉樹的最大結點數為2h-1個，
?性質三：對任何一棵二叉樹，如果度為0的葉結點個數為n0，度為2的分支結點個數為n2，則有n0 = n2+1，
?性質四：若規定根結點的層數為1，則具有N個結點的滿二叉樹的深度h = log2(N+1)，
?性質五：對于具有N個結點的完全二叉樹，如果按照從上至下、從左至右的陣列順序對所有結點從0開始編號，則對于序號為i的結點：
?若 i > 0，則該結點的父結點序號為：( i - 1) / 2；若 i = 0，則無父結點，
?若2i + 1 < N，則該結點的左孩子序號為：2i + 1；若2i + 1 >= N，則無左孩子，
?若2i + 2 < N，則該結點的右孩子序號為：2i + 2；若2i + 2 >= N，則無右孩子，
練習一下：
?1.某二叉樹共有399個結點，其中199個度為2的結點，則該二叉樹中的葉子結點數為（ ），
?A.不存在這樣的二叉樹
?B.200
?C.198
?D.199
?2.在具有2n個結點的完全二叉樹中葉子結點個數為（ ），
?A.n
?B.n+1
?C.n-1
?D.n/2
?3.一棵完全二叉樹的結點數為531，那么這棵樹的高度為（ ），
?A.11
?B.10
?C.8
?D.12
?4.一個具有767個結點的完全二叉樹，其葉子結點個數為（ ），
?A.383
?B.384
?C.385
?D.386
決議：
?1.（答案：B）根據性質三，葉子結點（度為0）的個數200個，由于199+200 = 399（該二叉樹的總結點數），所以該二叉樹的葉子結點數為200，
?2.（答案：A）根據性質三，度為0的結點數和度為2的結點數之和應為奇數，因為該完全二叉樹的結點總數為2n（偶數），所以二叉樹中必然存在一個度為1的結點，于是可以推出：度為0的結點和度為2的結點總共有2n-1個，性質三：對任何一棵二叉樹，度為0的葉結點個數比度為2的分支結點個數多1，所以該二叉樹度為1的結點個數為n-1，度為0的結點數（即葉結點數）為n，
?注意理解：任何一棵完全二叉樹中度為1的結點要么有1個，要么就沒有度為1的結點，因為完全二叉樹的最后一層的結點必須是從左到右連續的，而位于最后一層之前的層數的結點的度均為2，
?3.（答案：B）假設該完全二叉樹的層數為K，則該完全二叉樹的前K-1層的結點總數為2K-1-1，若該完全二叉樹是滿二叉樹，則該滿二叉樹的結點總數為2K-1，所以深度為K的完全二叉樹的結點總數范圍為：2K-1-1 < N <= 2K-1，因為29 < 531 <= 210，所以該完全二叉樹的高度為10，
?注意記憶：210 = 1024，
?4.（答案：B）該題與第2題的道理是一樣的，因為該樹的結點總數為767（奇數），所以該樹中不存在度為1的結點，度為2的結點個數為383，度為0的結點個數為384，即葉子結點個數為384，
二叉樹的存盤結構
順序結構
?順序結構存盤就是使用陣列來存盤，一般使用陣列只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費，而現實生活中只有堆（一種二叉樹）才會使用陣列來存盤，二叉樹的順序存盤在物理上是一個陣列，在邏輯上是一棵二叉樹，
鏈式結構
?二叉樹的鏈式存盤結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素之間的邏輯關系，通常的方法是鏈表中每個結點由三個域組成，資料域和左右指標域，左右指標分別用來存盤該結點左孩子和右孩子所在的結點的地址，
?鏈式結構又分為二叉鏈和三叉鏈，之后我們會用二叉鏈來實作二叉樹的鏈式存盤結構，三叉鏈運用于更高階的資料結構，例如紅黑樹，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/280696.html
標籤：其他
下一篇：wifi 無線密碼安全 1day