術(shù)語
位于樹頂部的節(jié)點(diǎn)叫作根節(jié)點(diǎn)（11）。它沒有父節(jié)點(diǎn)。
樹中的每個元素都叫作節(jié)點(diǎn)，節(jié)點(diǎn)分為內(nèi)部節(jié)點(diǎn)和外部節(jié)點(diǎn)。
鍵是樹相關(guān)的術(shù)語中對節(jié)點(diǎn)的稱呼。
至少有一個子節(jié)點(diǎn)的節(jié)點(diǎn)稱為內(nèi)部節(jié)點(diǎn)（7、5、9、15、13和20是內(nèi)部節(jié)點(diǎn)）。
沒有子元素的節(jié)點(diǎn)稱為外部節(jié)點(diǎn)或葉節(jié)點(diǎn)（3、6、8、10、12、14、18和25是葉節(jié)點(diǎn)）。
深度
節(jié)點(diǎn)的一個屬性是深度，節(jié)點(diǎn)的深度取決于它的祖先節(jié)點(diǎn)的數(shù)量。
比如，節(jié)點(diǎn)3有3個祖先節(jié)點(diǎn)（5、7和11），它的深度為3。
樹的高度
樹的高度取決于所有節(jié)點(diǎn)深度的最大值。
一棵樹也可以被分解成層級。根節(jié)點(diǎn)在第0層，它的子節(jié)點(diǎn)在第1層，以此類推。
上圖中的樹的高度為3（最大高度已在圖中表示——第3層）。
二叉樹
二叉樹中的節(jié)點(diǎn)最多只能有兩個子節(jié)點(diǎn)：一個是左側(cè)子節(jié)點(diǎn)，另一個是右側(cè)子節(jié)點(diǎn)。
二叉搜索樹（BST：Binary（二進(jìn)制、二元的） Search Tree）：左小右大
二叉搜索樹（BST）是二叉樹的一種，但是只允許你在左側(cè)節(jié)點(diǎn)存儲（比父節(jié)點(diǎn)）小的值，在右側(cè)節(jié)點(diǎn)存儲（比父節(jié)點(diǎn)）大的值。
樹的遍歷
中序、先序、后序
中序
從最小到最大
3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
先序
先序遍歷是以優(yōu)先于后代節(jié)點(diǎn)的順序訪問每個節(jié)點(diǎn)的
11 7 5 3 6 9 8 10 15 13 12 14 20 18 25
后序
序遍歷則是先訪問節(jié)點(diǎn)的后代節(jié)點(diǎn)，再訪問節(jié)點(diǎn)本身。
后序遍歷的一種應(yīng)用是計(jì)算一個目錄及其子目錄中所有文件所占空間的大小。
3 6 5 8 10 9 7 12 14 13 18 25 20 15 11
