資料結構之樹以及二叉樹的相關概念

樹

樹的基本概念

樹是一種非線性的資料結構，它是一種一對多的資料結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合，把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的

• 有一個特殊的結點，稱為根結點，根節點沒有前驅結點
• 除根節點外，其余結點被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i<= m)又是一棵結構與樹類似的子樹，每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼，因此，樹是遞回定義的，

樹的相關術語

節點的度： 一個節點含有的子樹的個數稱為該節點的度； 如上圖：A的為6
葉節點或終端節點： 度為0的節點稱為葉節點； 如上圖：B、C、H、I…等節點為葉節點
非終端節點或分支節點： 度不為0的節點； 如上圖：D、E、F、G…等節點為分支節點
雙親節點或父節點： 若一個節點含有子節點，則這個節點稱為其子節點的父節點； 如上圖：A是B的父節點
孩子節點或子節點： 一個節點含有的子樹的根節點稱為該節點的子節點； 如上圖：B是A的孩子節點
兄弟節點： 具有相同父節點的節點互稱為兄弟節點； 如上圖：B、C是兄弟節點
樹的度： 一棵樹中，最大的節點的度稱為樹的度； 如上圖：樹的度為6
節點的層次： 從根開始定義起，根為第1層，根的子節點為第2層，以此類推；
樹的高度或深度： 樹中節點的最大層次； 如上圖：樹的高度為4
堂兄弟節點： 雙親在同一層的節點互為堂兄弟；如上圖：H、I互為兄弟節點
節點的祖先： 從根到該節點所經分支上的所有節點；如上圖：A是所有節點的祖先
子孫： 以某節點為根的子樹中任一節點都稱為該節點的子孫，如上圖：所有節點都是A的子孫
森林： 由m（m>0）棵互不相交的樹的集合稱為森林；

樹的表示

樹結構相對線性表就比較復雜了，要存盤表示起來就比較麻煩了，既然保存值域，也要保存結點和結點之間的關系，實際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等，我們這里就簡單的了解其中最常用的孩子兄弟表示法，

typedef int DataType;
struct Node
{
    struct Node* _firstChild1; // 第一個孩子結點
    struct Node* _pNextBrother; // 指向其下一個兄弟結點
    DataType _data; // 結點中的資料域
};

每個結點都有指向它的孩子結點和它的下一個兄弟結點的指標，如上圖所示

樹在實際中的應用（表示檔案系統的目錄樹結構）

我們的磁盤下的檔案目錄系統就是樹的結構

二叉樹概念及結構

概念

二叉樹是n個結點的有限集合(n>=0)，該集合或者為空集(稱為空二叉樹)，或者由一個根結點和兩顆互不相交的、分別稱為根節點的左子樹和右子樹的二叉樹組成，

從上圖可以看出：

• 二叉樹不存在度大于2的結點
• 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹

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

特殊的二叉樹

• 滿二叉樹

一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹，也就是
說，如果一個二叉樹的層數為K，且結點總數是2^k -1，則它就是滿二叉樹，

例如這樣的一棵樹就是滿二叉樹：

注意：

滿二叉樹的節點的個數是：如果二叉樹的層數為K，則結點總數是2^k -1

• 完全二叉樹

完全二叉樹是效率很高的資料結構，完全二叉樹是由滿二叉樹而引出來的，對于深度為K
的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹， 要注意的是滿二叉樹是一種特殊的完全二叉樹，

簡而言之：完全二叉樹的前K-1層都是滿的，最后一層不一定滿，但是最后一層從左到右必須是連續的

例如：

注意：

完全二叉樹的節點的個數范圍是：

最多：2^k-1(滿二叉樹)

最少：2^(k-1)-1+1=2^(k-1)

二叉樹的性質

• 若規定根節點的層數為1.則一顆非空二叉樹的第i層最多有2^(i-1)個節點
• 若規定根節點的層數為1，則深度為h的二叉樹的最大結點數是2^h-1
• 對任何一棵二叉樹, 如果度為0其葉結點個數為n0 , 度為2的分支結點個數為n2,則有n0＝n2＋1
• 若規定根節點的層數為1，具有n個結點的滿二叉樹的深度，h=log2(n+1)， (ps： 是log以2
  為底，n+1為對數)

由滿二叉樹的節點數n=2^h-1，故深度h=log2(n+1)

我們下面來看幾個練習:

• 某二叉樹共有 399 個結點，其中有 199 個度為 2 的結點，則該二叉樹中的葉子結點數為（ ）
  A 不存在這樣的二叉樹
  B 200
  C 198
  D 199

由性質n0=n2+1，得n0=200，故葉子節點個數為200個

• 在具有 2n 個結點的完全二叉樹中，葉子結點個數為（ ）
  A n
  B n+1
  C n-1
  D n/2

該完全二叉樹有偶數個結點，說明有一個度為1的結點，有n0+n1+n2=2n，又n0=n2+1，n1=1，2n2+2=2n，解得n0=n，n2=n-1，故葉子結點個數為n

• 一棵完全二叉樹的節點數位為531個，那么這棵樹的高度為（ ）
  A 11
  B 10
  C 8
  D 12

設完全二叉樹的高度為h，總結點樹為n，由完全二叉樹的性質，高度為h的完全二叉樹結點最多為：n=2^h-1，高度h=log2(n+1)，結點最少為：n=2^(h-1)，當h=10時，結點最少為512個，最多為1023個，而531符合這個范圍，故這棵樹的高度為10

• 一個具有767個節點的完全二叉樹，其葉子節點個數為（）
  A 383
  B 384
  C 385
  D 386

因為完全二叉樹的總結點數為奇數，故這顆完全二叉樹不存在度為1的結點，故n0=n2+1，n0+n1+n2=767，得n2=383，故n1=384

二叉樹的存盤結構

• 順序存盤

順序結構存盤就是使用陣列來存盤，一般使用陣列只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費，而現實中使用中只有堆才會使用陣列來存盤，二叉樹順序存盤在物理上是一個陣列，在邏輯上是一顆二叉樹，

下標表示樹中父子關系公式：

leftchild = parent*2+1

rightchild = parent*2+2

parent=(child-1)/2

• 鏈式存盤

二叉樹的鏈式存盤結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系， 通常的方法是鏈表中每個結點由三個域組成，資料域和左右指標域，左右指標分別用來給出該結點左孩子和右孩子所在的鏈結點的存盤地址 ，鏈式結構又分為二叉鏈和三叉鏈

二叉鏈表結構：

typedef int BTDataType
struct BinaryTreeNode
{
    struct BinaryTreeNode* leftchild;//指向當前結點的左孩子
    struct BinaryTreeNode* rightchild;//指向當前結點的右孩子
    BTDataType data;
}

三叉鏈表結構：

typedef int BTDataType
struct BinaryTreeNode
{
    struct BinaryTreeNode* leftchild;//指向當前結點的左孩子
    struct BinaryTreeNode* rightchild;//指向當前結點的右孩子
    struct BinaryTreeNode* parent;//指向當前結點的雙親
    BTDataType data;
}

二叉樹的順序結構

普通的二叉樹是不適合用陣列來存盤的，因為可能會存在大量的空間浪費，而完全二叉樹更適合使用順序結構存盤，

歡迎大家互相學習！