一、樹的概念：

樹其實是區別於線性表，線性結構的另一種數據結構，本質是結點的有限集。樹的定義有兩點：1)有且僅有一個特定的稱為根（root）的結點；2）當結點數量>1時，其餘結點可分為若干個互不相交的有限集，其中每個集合也可以看作一顆樹，稱之為根的子樹。

1.度（結點的分類）：

結點擁有的子樹的數量是為樹的度。

如上圖所示，B結點的度為1，因為他只擁有根為D的一顆子樹，而D的度為3，因為他擁有G、H、I 三顆只有根的子樹，這就是結點的度，大家可以思考一下A結點的度是多少？

一顆樹的度則是這棵樹中度最多的結點的度的值，上面這顆樹的度則是D結點的度，為3。

2.結點之間的關係：

結點的子樹的根稱之為該結點的孩子（child結點）

該結點衍生出來的結點稱之為該結點的父母（parent結點）

由同一個結點衍生出的同一層結點互相稱之為兄弟（sibling）

由同一個結點之下的所有結點稱之為子孫，例如B的子孫有D、G、H、I 結點。

3.樹的層&深度：

如圖所示，結點的層次從根算起，根為第一層，根的孩子為第二層以此類推。

一棵樹的深度是樹中結點層次最大的值稱為樹的深度，或高度。

二、樹的存儲結構：

雙親孩子表示法：

把樹種的所有結點的值依次組成一個單鏈表，一個結點種定義三個域，分別是數據域、父母指針域、長子（第一個孩子）指針域，如果這個長子有兄弟的話，則指針域指向下一個存儲兄弟位置的指針域，否則就為空。

二、二叉樹：

1.二叉樹的定義：和樹的定義類似，但是有一個特點：由一個根節點和兩顆互不相交的，分別稱為根節點的左子樹和右子樹的二叉樹組成。（二叉樹是遞歸定義）

2.二叉樹的特點：1）每個結點最多有兩顆子樹；2）左子樹與右子樹有順序，即使一顆樹中只有一個子樹，也需要去判斷是左子樹還是右子樹。

3.一些特殊的二叉樹：1）斜樹：所有結點都只有左子樹或所有結點都只有右子樹的二叉樹稱為斜樹（斜樹其實就是單鏈表！）；2）滿二叉樹：如果一棵二叉樹的所有分支結點都存在左右子樹，並且所有的葉子結點都在同一層，則稱之為滿二叉樹；

3）完全二叉樹：如果每個結點按層序編號與相同層數的滿二叉樹編號一致的話，則這棵樹稱為滿二叉樹。

2.二叉樹的性質：

1）在二叉樹的第n層上最多有2^(n - 1)個結點。比如第一層：1個結點，第二層：2個 以此類推。

2）深度為k的二叉樹至多有2^k - 1 個結點，例如圖6-5-5的滿二叉樹有四層，結點有15個。數學歸納法可以證明。

3）一顆二叉樹的葉子結點樹為n，度為2的結點數量為m，則 n = m + 1；

證明過程：設一顆二叉樹的所有結點為n，度為1的結點為n1，度為2的結點是n2，葉子節點為n0，則：n = n1 + n2 + n0;因為二叉樹只有度為1或2的結點和葉子節點。而一顆二叉樹的所有連線可以根據二叉樹圖像直觀推出：n1 + n2 * 2 ；度為1的結點只有一條連線，度為2的結點有兩條連線，而一顆二叉樹的連線等於結點的數量減1，所以課可以列出式子： n1 + n2 + n0 - 1 = n1 + 2n2 可以得出性質3

4)具有n個結點的完全二叉樹深度為：log2n + 1可以根據性質2推出來。

5）對於一顆結點數量為n的完全二叉樹，n為樹的深度，i為按樹的層為結點編號，則：1.i = 1則此結點為根結點；2.若i > 2n 要麼此結點的左孩子是2i，否則不存在左孩子；3.與2類似，若i結點存在右孩子，則右孩子序號為 2i + 1;

3.二叉樹的存儲結構（重要）：

1）順序存儲結構：將二叉樹中的每一個結點按照滿二叉樹的層次序號進行編號，將空著的編號進行留空，將結點中的數據存入數組對應編號中，這樣可以做成二叉樹的順序存儲結構。

但是缺點是浪費存儲空間，舉個例子：斜二叉樹的順序存儲結構會是怎麼樣的呢？

如圖所示，浪費了非常多的存儲空間，所以順序存儲結構只適用於完全二叉樹。

2）二叉鏈表：

首先樹結點定義與結點定義類似，但是指針域有兩個，分別是lchild（左孩子）和rchild（右孩子）。如圖所示：

樹的定義與單鏈表定義有相似之處，就是必須要有根節點。

樹的創造方法：（while方法，非遞歸）

用類似於棧的思想進行樹的創建，其實和遞歸類似，遞歸也是用到棧。

4.二叉樹的遍歷：

眾所周知二叉樹的三種遍歷方法：前序遍歷、中序遍歷、後序遍歷；其實還有一種層序遍歷，就是按照一層一層從左到右的順序依次遍歷樹。、

1）前序遍歷：

2）中序遍歷：

3）後序遍歷：

其實遞歸遍歷的核心思想是理解遞歸，關於這一點大家可以去看一下我寫的遞歸和棧的那篇文章，有詳細的解釋。


推薦閱讀：
相關文章