1、樹的概念及結構(了解)

1.1樹的概念：

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

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

子樹是不相交的；除了根節點之外，每個節點有且僅有一個父節點；一棵N個節點的樹有N-1條邊。

節點的度：一個節點含有的子樹的個數稱為該節點的度； 如上圖：A的為3

葉節點或終端節點：度為0的節點稱為葉節點； 如上圖：J、F、K、L、H、I節點為葉節點

非終端節點或分支節點：度不為0的節點； 如上圖：B、C、D、E..等節點為分支節點

雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點； 如上圖：A是B的父節點

孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點； 如上圖：B是A的孩子節點

兄弟節點：具有相同父節點的節點互稱為兄弟節點； 如上圖：B、C是兄弟節點

樹的度：一棵樹中，最大的節點的度稱為樹的度； 如上圖：樹的度為3

節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；

樹的高度或深度：樹中節點的最大層次； 如上圖：樹的高度為4

節點的祖先：從根到該節點所經分支上的所有節點；如上圖：A是所有節點的祖先

子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫。如上圖：所有節點都是A的子孫

森林：由m（m>0）棵互不相交的多顆樹的集合稱為森林；（數據結構中的學習并查集本質就是 一個森林）

1.2樹的表示法：

??樹結構相對線性表就比較復雜了，要存儲表示起來就比較麻煩了，實際中樹有很多種表示方式， 如：雙親表示法，孩子表示法、孩子兄弟表示法等等。我們這里就簡單的了解其中最常用的孩子 兄弟表示法。(我們本期主要講解二叉樹)

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

2、二叉樹的概念及結構

2.1二叉樹的概念

一棵二叉樹是結點的一個有限集合，該集合或者為空，或者是由一個根節點加上兩棵別稱為左子 樹和右子樹的二叉樹組成。

二叉樹的特點：

1. 每個結點最多有兩棵子樹，即二叉樹不存在度大于2的結點。

2. 二叉樹的子樹有左右之分，其子樹的次序不能顛倒。

2.2特殊的二叉樹

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

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

2.2二叉樹的性質

1、若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有2^(i-1) 個結點.

2、若規定根節點的層數為1，則深度為h的二叉樹的最大結點數是2^h- 1.

3、對任何一棵二叉樹, 如果度為0其葉結點個數為 n0, 度為2的分支結點個數為 n2,則有n0＝n2 + 1.

2.3二叉樹的順序存儲

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

2.4二叉樹的鏈式存儲

二叉樹的鏈式存儲結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。 通常的方法是鏈表中每個結點由三個域組成，數據域和左右指針域，左右指針分別用來給出該結點左孩子和右孩子所在的鏈結點的存儲地址 。鏈式結構又分為二叉鏈和三叉鏈，我們本期用的是二叉鏈，后期到高階數據結構如紅黑樹等會用到三叉鏈。

代碼結構搭建：

typedef char BTDataType;
typedef struct BinaryTreeNode
{
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
    BTDataType data;
}BTNode;

3、二叉樹鏈式結構的實現

3.1二叉樹的前中后序遍歷

如果這個地方看不明白的可以去畫遞展開歸圖，如果畫展開遞歸圖還不明白就得去復習下C語言的遞歸章節了！

3.2求二叉樹的節點個數

同理我們一樣可以使用遞歸的方法：

int TreeSize(BTNode* root)
{
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

3.3求二叉樹的葉子節點個數

int TreeLeafSize(BTNode* root)
{
    if (root == NULL)
        return 0;
    if (root->left == NULL && root->right == NULL)
        return 1;
    return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

3.4銷毀二叉樹

void DestoryTree(BTNode* root)
{
    if (root == NULL)
        return;
    DestoryTree(root->left);
    DestoryTree(root->right);
 
    free(root);
    root = NULL;
}

還剩一個二叉樹的層序遍歷，我把思路給大家講一下，看完了可以自己去實現一下，如果實現不了或者有疑問隨時可以聯系我哦！

層序遍歷：設二叉樹的根節點所在層數為1，層序遍歷就是從所在二叉樹的根節點出發，首先訪問第一層的樹根節點，然 后從左到右訪問第2層上的節點，接著是第三層的節點，以此類推，自上而下，自左至右逐層訪問 樹的結點的過程就是層序遍歷。

可以借助棧來實現，上一層帶下一層的思路！

二叉樹的實現到這里就結束了，可能小伙伴還有疑問，為什么二叉樹沒有增刪查改，因為用二叉樹進行增刪查改是沒意義的，搜索二叉樹才是需要用到的，再者像復雜的VAL樹和紅黑樹就得等到后期講完C++配合著C++一起講了，這只是非線性的入門！