?

1.樹概念及結構

1.1樹的概念

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

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

?注意：樹形結構中，子樹之間不能有交集，否則就不是樹形結構

1.2 樹的相關概念

節點的度：一個節點含有的子樹的個數稱為該節點的度； 如上圖：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）棵互不相交的樹的集合稱為森林；

1.3 樹的表示

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

樹的孩子兄弟表示法（Child-sibling representation）也被稱為左孩子右兄弟表示法，它是一種用于表示樹結構的方法。在這種表示法中，每個節點包含兩個指針：一個指向其第一個子節點，另一個指向它的下一個兄弟節點。

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

?

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

?

2.二叉樹概念及結構

2.1概念

一棵二叉樹是結點的一個有限集合，該集合:

1. 或者為空

2. 由一個根節點加上兩棵別稱為左子樹和右子樹的二叉樹組成

?從上圖可以看出：

1. 二叉樹不存在度大于2的結點

2. 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹

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

?

2.2 特殊的二叉樹

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

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

?

2.3?二叉樹的性質

?

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

?解析：葉子節點是度為0的節點，根據上面的性質3：

?所以葉子節點=199+1=200；

答案：B

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

解析：

答案：B

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

?解析：

?答案：B

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

?解析：?

??答案：B

2.4 二叉樹的存儲結構

二叉樹一般可以使用兩種結構存儲，一種順序結構，一種鏈式結構。

1. 順序存儲

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

?2. 鏈式存儲

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

?

?