目錄

1.樹的概念

父子結點

根節點|葉節點

結點的度

葉子結點或終端結點

兄弟結點

樹的度

結點的層次

樹的高度或深度

結點的祖先

堂兄弟結點

子孫

森林

2. 樹的結構定義

2.1 左孩子右兄弟結構

2.2 數組表示法

3.樹&非樹

---

1.樹的概念

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

我們發現樹是有一個一個節點構成的，如果一個節點都沒有，我們稱作“空樹”。

父子結點

????????通常由一個結點延伸出來的直接結點稱作該結點的子結點；例如下圖中：1號結點是2號結點的父結點，2號結點是1號結點的子結點。

根節點|葉節點

? ? ? ? 沒有父結點的結點稱為根結點；

? ? ? ? 沒有子結點的結點稱為葉結點。

結點的度

一個結點含有的子樹的個數稱為該結點的度，上圖A的度為6；

葉子結點或終端結點

度為0的節點稱為葉結點，上圖BCHIPQKLMN，都是葉結點。

兄弟結點

擁有相同的父結點的結點稱為兄弟結點，例如KLM是兄弟結點。

樹的度

最大結點的度稱為樹的度，上圖中樹的度是6

結點的層次

從根開始，根為第一層，根的子結點稱為第2層，以此類推。

樹的高度或深度

樹中結點層次最大的。如上圖樹的高度為4；

結點的祖先

從根到該結點經過的所有結點，如上圖A是所有結點的祖先，P的祖先是AEJ；

堂兄弟結點

雙親在同一層的結點互為堂兄弟結點，例如HI是堂兄弟結點。

子孫

以某節點為根的子樹都叫做該結點的子孫。

森林

由M（M>0）棵互不相交的樹的集合稱為森林。

2. 樹的結構定義

? ? ? ? 當已知數的度是多少的情況下可以定義樹的結構：

#define _CRT_SECURE_NO_WARNINGS
#define N 3 // 假設度為3
typedef struct TreeNode 
{int val;struct TreeNode* child1[N];
}TreeNode;

????????在windows文件資源管理器中，其實就是一棵樹，盤符是根結點，但是這棵樹沒有規定究竟有多少個子節點，也就是說這里沒有提前定義這棵樹的度。上面那種定義會存在一定程度上的內存浪費。

? ? ? ? 我們可以使用順序表來存，順序表的每一個元素都是一個結點的指針，這種定義的方式顯然也不夠好,在底層也會有一定程度的空間浪費。

typedef struct TreeNode 
{int val;TreeNodeSeqList childs;
}TreeNo

2.1 左孩子右兄弟結構

? ? ? ? 在樹中有一種非常清晰明了的結構，結構體中存有兩個指針，一個指針指向左邊第一個孩子，第二個指針指向它的兄弟（親兄弟）。

typedef struct TreeNode 
{int val;TreeNode LeftChild;TreeNode RightBrother;
}TreeNode;

如圖：

我們使用左孩子右兄弟的表示方法表示上面的樹：

通過訪問根結點的左邊第一個孩子，再通過訪問它的右兄弟就能將A節點的所有孩子全部訪問。

2.2 數組表示法

定義兩個數組，第一個數組是存放所有的結點；

第二個數組根據每一個結點存放對應的父結點的下標。

例如A沒有父結點，存-1；

B、C的父結點是A，存A的下標0......

3.樹&非樹

①子樹是不相交的。

②每一個結點有且只有一個父結點。

③N個節點有N-1條邊。

只需要看樹是否構成回路。