一、什么是單支樹(shù)

單支樹(shù)是非葉子節(jié)點(diǎn)只有一個(gè)孩子節(jié)點(diǎn)，且方向一致的特殊二叉樹(shù)。單支樹(shù)指的是只有一個(gè)孩子并且方向一致，就是每個(gè)結(jié)點(diǎn)非常多只有一個(gè)孩子結(jié)點(diǎn)，其實(shí)就是鏈表。

二叉樹(shù)是另一種樹(shù)形結(jié)構(gòu)，其特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有兩棵子樹(shù)( 即二叉樹(shù)中不存在度大于2的結(jié)點(diǎn))，并且二叉樹(shù)的子樹(shù)有左右之分，其次序不能任意顛倒。

與樹(shù)相似，二叉樹(shù)也以遞歸的形式定義。二叉樹(shù)是n (n≥0) 個(gè)結(jié)點(diǎn)的有限集合:

或者為空二叉樹(shù)，即n=0。

或者由一個(gè)根結(jié)點(diǎn)和兩個(gè)互不相交的被稱(chēng)為根的左子樹(shù)和右子樹(shù)組成。左子樹(shù)和右子樹(shù)又分別是一棵二叉樹(shù)。

二叉樹(shù)是有序樹(shù)，若將其左、右子樹(shù)顛倒，則成為另一棵不同的二叉樹(shù)。即使樹(shù)中結(jié)點(diǎn)只有一棵子樹(shù)，也要區(qū)分它是左子樹(shù)還是右子樹(shù)。

延伸閱讀：

二、幾個(gè)特殊的二叉樹(shù)

（1）斜樹(shù)

所有的結(jié)點(diǎn)都只有左子樹(shù)的二叉樹(shù)叫左斜樹(shù)。所有結(jié)點(diǎn)都是只有右子樹(shù)的二叉樹(shù)叫右斜樹(shù)。這兩者統(tǒng)稱(chēng)為斜樹(shù)。

（2）滿二叉樹(shù)棵高度為h，且含有2 h ? 1 2^h-12h?1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱(chēng)為滿二叉樹(shù)，即樹(shù)中的每層都含有非常多的結(jié)點(diǎn)。滿二叉樹(shù)的葉子結(jié)點(diǎn)都集中在二叉樹(shù)的最下一層，并且除葉子結(jié)點(diǎn)之外的每個(gè)結(jié)點(diǎn)度數(shù)均為2 22。可以對(duì)滿二叉樹(shù)按層序編號(hào):約定編號(hào)從根結(jié)點(diǎn)(根結(jié)點(diǎn)編號(hào)為1 11)起，自上而下，自左向右。這樣，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)編號(hào),對(duì)于編號(hào)為i的結(jié)點(diǎn)，若有雙親，則其雙親為i / 2 i/2i/2,若有左孩子，則左孩子為2 i 2i2i;若有右孩子，則右孩子為2 i + 1 2i+12i+1。