什么是”樹“

樹（tree）是包含n（n>0）個(gè)結(jié)點(diǎn)的有窮集造寝，其中：
（1）每個(gè)元素稱為結(jié)點(diǎn)（node）
（2）有一個(gè)特定的結(jié)點(diǎn)被稱為根結(jié)點(diǎn)或樹根（root）
（3）除根結(jié)點(diǎn)之外的其余數(shù)據(jù)元素被分為m（m≥0）個(gè)互不相交的集合T1垂睬，T2整陌，……Tm-1说搅，其中每一個(gè)集合Ti（1<=i<=m）本身也是一棵樹静浴，被稱作原樹的子樹（subtree）击儡。
樹也可以這樣定義：樹是由根結(jié)點(diǎn)和若干顆子樹構(gòu)成的术奖。樹是由一個(gè)集合以及在該集合上定義的一種關(guān)系構(gòu)成的站楚。集合中的元素稱為樹的結(jié)點(diǎn)脱惰，所定義的關(guān)系稱為父子關(guān)系。父子關(guān)系在樹的結(jié)點(diǎn)之間建立了一個(gè)層次結(jié)構(gòu)窿春。在這種層次結(jié)構(gòu)中有一個(gè)結(jié)點(diǎn)具有特殊的地位拉一，這個(gè)結(jié)點(diǎn)稱為該樹的根結(jié)點(diǎn)采盒，或稱為樹根。
我們可以形式地給出樹的遞歸定義如下:
單個(gè)結(jié)點(diǎn)是一棵樹蔚润，樹根就是該結(jié)點(diǎn)本身磅氨。
設(shè)T1,T2,..,Tk是樹，它們的根結(jié)點(diǎn)分別為n1,n2,..,nk嫡纠。用一個(gè)新結(jié)點(diǎn)n作為n1,n2,..,nk的父親烦租，則得到一棵新樹，結(jié)點(diǎn)n就是新樹的根除盏。我們稱n1,n2,..,nk為一組兄弟結(jié)點(diǎn)叉橱，它們都是結(jié)點(diǎn)n的子結(jié)點(diǎn)。我們還稱T1,T2,..,Tk為結(jié)點(diǎn)n的子樹痴颊。
空集合也是樹赏迟，稱為空樹〈览猓空樹中沒有結(jié)點(diǎn)。

相關(guān)概念：

• 節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)成為該節(jié)點(diǎn)的度
• 葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為0的節(jié)點(diǎn)成為葉節(jié)點(diǎn)
• 非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)
• 雙親節(jié)點(diǎn)或者父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)甩栈，則這個(gè)節(jié)點(diǎn)成為其子節(jié)點(diǎn)的父節(jié)點(diǎn)
• 孩子節(jié)點(diǎn)或者子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)
• 兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)
• 節(jié)點(diǎn)的層次：從根節(jié)點(diǎn)定義起泻仙，根節(jié)點(diǎn)為第一層，根節(jié)點(diǎn)的子節(jié)點(diǎn)為第二層量没，以此類推
• 樹的高度或深度：樹中最大的層次
• 堂兄弟節(jié)點(diǎn)：雙親在同一層的節(jié)點(diǎn)互稱堂兄弟
• 節(jié)點(diǎn)的祖先：從根節(jié)點(diǎn)到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)
• 子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都成為該節(jié)點(diǎn)的子孫

樹的種類：

• 無序樹：樹中任意節(jié)點(diǎn)的子結(jié)點(diǎn)之間沒有順序關(guān)系玉转，這種樹稱為無序樹,也稱為自由樹
• 有序樹：樹中任意節(jié)點(diǎn)的子結(jié)點(diǎn)之間有順序關(guān)系，這種樹稱為有序樹
• 二叉樹：每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子樹的樹稱為二叉樹
• 滿二叉樹:除最后一層無任何子節(jié)點(diǎn)外殴蹄，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)二叉樹究抓。
• 完全二叉樹:　若設(shè)二叉樹的深度為h，除第 h 層外袭灯，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)刺下，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹稽荧。完全二叉樹是由滿二叉樹而引出來的橘茉。對(duì)于深度為K的，有N個(gè)結(jié)點(diǎn)的二叉樹姨丈，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱之為完全二叉樹.若一棵二叉樹至多只有最下面的兩層上的結(jié)點(diǎn)的度數(shù)可以小于2畅卓，并且最下層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹成為完全二叉樹蟋恬。
• 霍夫曼樹：帶權(quán)路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹

樹的遍歷：

1. 先序遍歷：從根節(jié)點(diǎn)開始翁潘，先遍歷左子樹，然后遍歷右子樹歼争，在遍歷子樹的時(shí)候拜马，依舊按照從根節(jié)點(diǎn)遍歷左右子樹的原則遍歷(A,B,D,E,C,F)
2. 中序遍歷：從最左的葉子節(jié)點(diǎn)開始箱歧，先遍歷左節(jié)點(diǎn)，然后根節(jié)點(diǎn)一膨，再右節(jié)點(diǎn)(D,B,E,A,F,C)
3. 后序遍歷：從最左的葉子節(jié)點(diǎn)開始呀邢，先遍歷左節(jié)點(diǎn)，然后右節(jié)點(diǎn)豹绪，再跟節(jié)點(diǎn)(D,E,B,F,C,A)

二叉樹:

對(duì)樹而言价淌，需要重點(diǎn)掌握二叉樹。二叉樹是一種特殊的順序樹瞒津，它規(guī)定有左右兩個(gè)孩子蝉衣，即左右孩子順序不能替換，所以二叉樹是一種有序樹巷蚪。二叉樹的結(jié)點(diǎn)數(shù)為大于0小于等于2病毡。

二叉樹性質(zhì)：

對(duì)樹而言，需要重點(diǎn)掌握二叉樹屁柏。二叉樹是一種特殊的順序樹啦膜，它規(guī)定有左右兩個(gè)孩子，即左右孩子順序不能替換淌喻，所以二叉樹是一種有序樹僧家。二叉樹的結(jié)點(diǎn)數(shù)為大于0小于等于2。對(duì)于二叉樹裸删，需要掌握以下性質(zhì)：

性質(zhì)1:
在二叉樹的第i層上至多有

性質(zhì)2:
深度為K的二叉樹至多有

性質(zhì)3:
二叉樹中旦棉，終端結(jié)點(diǎn)

(1)

(3)

(4)

           1
         /   \
       2       3
     /   \   /   \
    4     5 6     7

完全二叉樹：深度為k,結(jié)點(diǎn)數(shù)為n的二叉樹左敌，當(dāng)且僅當(dāng)每個(gè)結(jié)點(diǎn)的編號(hào)都與相同深度的滿二叉樹中從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為完全二叉樹俐镐。

                          1
                         / \
                        2   3
                       / \ 
                      4   5   （注意編號(hào)順序叼风，與滿二叉樹一一對(duì)應(yīng)）

(向下取整)+ 1
由性質(zhì)2及完全二叉樹的定義有：
結(jié)點(diǎn)數(shù)滿足：

性質(zhì)6: 含有n個(gè)結(jié)點(diǎn)的二叉鏈表中溉卓，有n + 1個(gè)空鏈域。

(1)

(2)