一、什么是單支樹
單支樹是非葉子節點只有一個孩子節點,且方向一致的特殊二叉樹。單支樹指的是只有一個孩子并且方向一致,就是每個結點非常多只有一個孩子結點,其實就是鏈表。
二叉樹是另一種樹形結構,其特點是每個結點至多只有兩棵子樹( 即二叉樹中不存在度大于2的結點),并且二叉樹的子樹有左右之分,其次序不能任意顛倒。
與樹相似,二叉樹也以遞歸的形式定義。二叉樹是n (n≥0) 個結點的有限集合:
或者為空二叉樹,即n=0。
或者由一個根結點和兩個互不相交的被稱為根的左子樹和右子樹組成。左子樹和右子樹又分別是一棵二叉樹。
二叉樹是有序樹,若將其左、右子樹顛倒,則成為另一棵不同的二叉樹。即使樹中結點只有一棵子樹,也要區分它是左子樹還是右子樹。
延伸閱讀:
二、幾個特殊的二叉樹
(1)斜樹
所有的結點都只有左子樹的二叉樹叫左斜樹。所有結點都是只有右子樹的二叉樹叫右斜樹。這兩者統稱為斜樹。
(2)滿二叉樹棵高度為h,且含有2 h ? 1 2^h-12h?1個結點的二叉樹稱為滿二叉樹,即樹中的每層都含有非常多的結點。滿二叉樹的葉子結點都集中在二叉樹的最下一層,并且除葉子結點之外的每個結點度數均為2 22。可以對滿二叉樹按層序編號:約定編號從根結點(根結點編號為1 11)起,自上而下,自左向右。這樣,每個結點對應一個編號,對于編號為i的結點,若有雙親,則其雙親為i / 2 i/2i/2,若有左孩子,則左孩子為2 i 2i2i;若有右孩子,則右孩子為2 i + 1 2i+12i+1。