樹概念及結構

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

注意：

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

如圖：

注意：

• 樹形結構中，子樹之間不能有交集，否則就不是樹形結構
• 除了根節點外，每個節點有且只有一個父節點
• 一棵樹N個節點的樹有N-1條邊

相關概念

如圖：

• 節點的度：一個節點含有的子樹的個數稱為該節點的度； 如上圖：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; // 結點中的數據域
};

如圖：

樹在實際中的運用（表示文件系統的目錄樹結構）

二叉樹概念及結構

概念

• 二叉樹由一個根節點加上左子樹和右子樹組成：
• 二叉樹度最大為2（度可以為0,1,2）
• 二叉樹的子樹有左右之分，次序不能顛倒（有序樹）（沒有左樹，一定沒有右樹；有左樹，不一定有右樹）

需要注意的特殊二叉樹

滿二叉樹：

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

完全二叉樹：

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

二叉樹的性質

• 若規定根節點的層數為 1 ，則一棵非空二叉樹的 第 i 層上最多有2^（i-1）個結點
• 若規定根節點的層數為 1 ，則 深度為 h的二叉樹的最大結點數是2^h-1
• 若規定根節點的層數為1，具有n個結點的滿二叉樹的深度，h=log2（n+1）（是log以2為底，n+1為對數）

二叉樹的存儲結構

存儲結構類型：

順序存儲

順序結構存儲就是使用 數組來存儲 ，一般使用數組只適合表示完全二叉樹（不完全二叉樹有空間的浪費）而現實中使用中只有堆才會使用數組來存儲

注：二叉樹順序存儲在物理上是一個數組，在邏輯上是一顆二叉樹

如圖：

鏈式存儲

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

例：

typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{
    struct BinTreeNode* _pLeft; // 指向當前節點左孩子
    struct BinTreeNode* _pRight; // 指向當前節點右孩子
    BTDataType _data; // 當前節點值域
}

// 三叉鏈
struct BinaryTreeNode
{
 struct BinTreeNode* _pParent; // 指向當前節點的雙親
 struct BinTreeNode* _pLeft; // 指向當前節點左孩子
 struct BinTreeNode* _pRight; // 指向當前節點右孩子
 BTDataType _data; // 當前節點值域
}；

總結

這只是二叉樹的基本知識，之后我們還會詳細解析二叉數的遞歸實現和有關題目。