? ? 在日常生活中或者開發(fā)中我們經(jīng)常會用到一些樹形結(jié)構(gòu)(例如：二叉樹、多叉樹見 附圖1)。為什么要用到樹結(jié)構(gòu)呢，是因為使用樹形結(jié)構(gòu)可以很快速、清晰的去對應(yīng)的樹節(jié)點內(nèi)去查找需要的數(shù)據(jù)，這樣就大大的提高了效率。
二叉樹 、多叉樹
附圖1:
樹結(jié)構(gòu)中的元素概念
附圖2:
節(jié)點：
樹上的每個分叉點的元素。
「附圖2 」中的 1、2、...... 14、15 都是節(jié)點
根節(jié)點 ：
一棵樹最多只有一個根結(jié)點，即最開始分叉的節(jié)點。
「附圖2 」中的 1節(jié)點是其他節(jié)點的根節(jié)點
注意：
- 一棵樹可以沒有任何節(jié)點，稱之為
空樹- 一棵樹可以只有一個節(jié)點，也就是
根節(jié)點
父節(jié)點 ：
樹中分叉的那一個節(jié)點
例子：
「附圖2 」中的 1節(jié)點是 2節(jié)點和 3節(jié)點的父節(jié)點； 2節(jié)點是 4節(jié)點和 5節(jié)點的父節(jié)點
子節(jié)點 ：
樹中某一個節(jié)點分叉出去的下一級節(jié)點
例子：
「附圖2 」中的 2節(jié)點和 3節(jié)點是 1節(jié)點的子節(jié)點；4節(jié)點和 5節(jié)點是 2節(jié)點的子節(jié)點
兄弟節(jié)點 ：
樹中某一個節(jié)點分叉出去的下一級節(jié)點中的同一級的節(jié)點，即同一級的節(jié)點有 相同的父節(jié)點
例子：
「附圖2 」中的 2節(jié)點和 3節(jié)點是 相互的兄弟節(jié)點； 4節(jié)點和 5節(jié)點是 相互的兄弟節(jié)點
注意 : 8節(jié)點和 10節(jié)點是 相互的兄弟節(jié)點, 因為8節(jié)點和 10節(jié)點沒有相同的父節(jié)點
子樹 ：
樹中某一個節(jié)點分叉出去的下一級節(jié)點上的某一個節(jié)點下的所有節(jié)點組成的樹
例子：
「附圖2 」中的 2節(jié)點和其 往下的所有節(jié)點 就是1 節(jié)點的子樹（2、4、5、8、9、10、11這些節(jié)點組成的樹是 1節(jié)點的一個子樹）
3節(jié)點和其 往下的所有節(jié)點 就是1 節(jié)點的子樹（3、6、7、12、13、14、15這些節(jié)點組成的樹是 1節(jié)點的子樹）
4節(jié)點和其 往下的所有節(jié)點 就是2節(jié)點的子樹（ 4、8、9、這些節(jié)點組成的樹是 2節(jié)點的一個子樹）
5節(jié)點和其 往下的所有節(jié)點 就是2節(jié)點的子樹（ 5、10、11、這些節(jié)點組成的樹是 2節(jié)點的另一個子樹）
左子樹 ：
樹中某一個節(jié)點分叉出去的下一級節(jié)點上的左側(cè)的一個節(jié)點下的所有節(jié)點組成的樹
例子：
「附圖2 」中的 2節(jié)點和其 往下的所有節(jié)點 就是1 節(jié)點的左子樹（2、4、5、8、9、10、11這些節(jié)點組成的樹是 1節(jié)點的左子樹）
4節(jié)點和其 往下的所有節(jié)點 就是2 節(jié)點的左子樹（4、8、9、這些節(jié)點組成的樹是 2節(jié)點的左子樹）
右子樹 ：
樹中某一個節(jié)點分叉出去的下一級節(jié)點上的右側(cè)的一個節(jié)點下的所有節(jié)點組成的樹
例子：
「附圖2 」中的 3節(jié)點和其 往下的所有節(jié)點 就是1 節(jié)點的右子樹（3、6、7、12、13、14、15這些節(jié)點組成的樹是 1節(jié)點的右子樹）
5節(jié)點和其 往下的所有節(jié)點 就是2節(jié)點的右子樹（ 5、10、11、這些節(jié)點組成的樹是 2節(jié)點的右子樹）
附圖3:
節(jié)點的度（degree） ：
子樹的個數(shù)
例子：
「附圖3 」中的 B(2)節(jié)點的度為2 ；K(11)節(jié)點的度為3；E(5)節(jié)點的度為0
樹的度（degree） ：
所有節(jié)點度 中的最大值
例子：
「附圖3 」中的 A(1)節(jié)點的度為5 是所有節(jié)點中擁有最大的度，所以樹的度就是5
葉子節(jié)點 ：
度為0的節(jié)點
例子：
「附圖3 」中 的E(5)、J(10)、L(12)、P(16)、Q(17)節(jié)點 的度為0就是葉子節(jié)點
非葉子節(jié)點 ：
度不為0的節(jié)點
邊數(shù) ：
當(dāng)前節(jié)點到下一個字節(jié)點的路徑
根節(jié)點沒有邊
例子：
「附圖3 」中 的A(1)節(jié)點到B(2)節(jié)點的路徑是一條邊；B(2)節(jié)點到H(7)節(jié)點的路徑是一條邊
層數(shù) ：
每一個節(jié)點和其子節(jié)點所在的位置層級。根結(jié)點在第一層，根結(jié)點的子節(jié)點在第二層，依次類推（也有的是從0層開始計算的）
例子:
「附圖3 」中 的A(1)節(jié)點 是第一層；A(1) 的子節(jié)點B(2)、C(3)、D(4)、E(5)、F(6)節(jié)點是第二層; H(7)、I(9)、J(10)、K(11)、L(12)、M(13)、N(14)節(jié)點是第三層; O(15)、P(16)、Q(17)、R(18)、S(19)、T(20)節(jié)點是第四層; 所以這棵樹共有四層
節(jié)點的深度 ：
從根節(jié)點到當(dāng)前節(jié)點的最短的唯一直達(dá)路徑上的節(jié)點總數(shù)
例子:
「附圖3 」中 的B(2)節(jié)點深度是2，即（從A(1)根節(jié)點到B(2)節(jié)點的唯一直達(dá)路徑上的節(jié)點只有A(1) 、B(2)共計2個節(jié)點，總數(shù)為2）；
C(3)節(jié)點深度是2，即（從A(1)根節(jié)點到C(3)節(jié)點的唯一直達(dá)路徑上的節(jié)點只有A(1) 、C(3)共計2個節(jié)點，總數(shù)為2）；
O(15)節(jié)點深度是4，即（從A(1)根節(jié)點到O(15)節(jié)點的唯一直達(dá)路徑上的節(jié)點有：A(1) 、B(2)、H(7) 、O(15)共計4個節(jié)點）；
節(jié)點的高度 ：
從當(dāng)前節(jié)點到其子樹上最遠(yuǎn)的葉子節(jié)點的最短的唯一直達(dá)路徑上的節(jié)點總數(shù)
例子：
「附圖3 」中 的C(3)節(jié)點高度是3，即從C(3)節(jié)點到其子樹上最遠(yuǎn)的Q(17)葉子節(jié)點的最短路徑上的節(jié)點有C(3)、I(9)、Q(17)共計3個節(jié)點；J(10)、Q(17)都是葉子節(jié)點。
D(4)節(jié)點高度是3，即從D(4)節(jié)點到其子樹上最遠(yuǎn)的R(18)葉子節(jié)點的最短路徑上的節(jié)點有D(4)、K(11)、R(18)共計3個節(jié)點; L(12)、R(18)、S(19)、T(20)都是葉子節(jié)點，R(18)、S(19)、T(20)三個葉子節(jié)點是同一層級。
注意：
- 深度和高度的區(qū)別
深度是 從根節(jié)點到當(dāng)前節(jié)點的路徑上的節(jié)點總數(shù)；高度是 從當(dāng)前節(jié)點到其子樹上最遠(yuǎn)的葉子節(jié)點路徑上的節(jié)點總數(shù)
樹的深度 ：
所有節(jié)點深度中的最大值
例子
「附圖3 」中 的O(15)節(jié)點深度是4， 是這棵樹最大的深度值，所以這棵樹的深度是4
樹的高度 ：
所有節(jié)點高度中的最大值
例子
「附圖3 」中 的A(1)根節(jié)點高度是4， 是這棵樹最大的高度值，所以這棵樹的高度是4
樹的深度 等于 樹的高度
有序樹：
樹的任意節(jié)點下的子節(jié)點之間都是有順序關(guān)系的。（如下附圖4）
無序樹、自由樹：
樹的任意節(jié)點下的子節(jié)點之間都是沒有順序關(guān)系的。（如下附圖5）
森林：
由 m（m ≥ 0）顆互不想交的樹組成的集合。
