C語言深入淺出解析二元樹

2022-03-30 19:04:00

樹概念及結構

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

注意：

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

如圖：

注意：

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

樹的表示

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

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; // 當前節點值域
}；