一、什么是單支樹(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。