一、什么是單支樹

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

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

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

或者為空二叉樹，即n=0。

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

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

延伸閱讀：

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

（1）斜樹

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

（2）滿二叉樹棵高度為h，且含有2 h ? 1 2^h-12h?1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹，即樹中的每層都含有非常多的結(jié)點(diǎn)。滿二叉樹的葉子結(jié)點(diǎn)都集中在二叉樹的最下一層，并且除葉子結(jié)點(diǎn)之外的每個(gè)結(jié)點(diǎn)度數(shù)均為2 22。可以對(duì)滿二叉樹按層序編號(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。