一、二叉樹各結(jié)點的度
二叉樹各結(jié)點的度是指樹中所以結(jié)點的度數(shù)的最大值。二叉樹的度小于等于2,因為二叉樹的定義要求二叉樹中任意結(jié)點的度數(shù)(結(jié)點的分支數(shù))小于等于2。
節(jié)點度就是這個節(jié)點的孩子數(shù)量,例如有左右孩子的節(jié)點,它的度為2,如果只有左孩子或者只有右孩子的節(jié)點,它的度就是1,葉節(jié)點就是度為0的節(jié)點(沒有孩子)。
先序遍歷的話,只要孩子不是NULL,就可以將這個節(jié)點的度+1。比如這張圖,以節(jié)點3為例,它的左孩子是6,度+1,現(xiàn)在度為1。右孩子沒有,即NULL,不做任何操作。所以節(jié)點3的度為1。
二叉樹是樹形結(jié)構(gòu)中一種特殊的樹形結(jié)構(gòu):二叉樹中的每個結(jié)點至多有2棵子樹(即每個結(jié)點的度小于等于2),并且兩個子樹有左右之分,順序不可顛倒。在二叉樹中還有種特殊的二叉樹就是完全二叉樹:所有結(jié)點中除了葉子結(jié)點以外的結(jié)點都有兩棵子樹。如果完全二叉樹中只有最底層為葉子結(jié)點那么又稱為滿二叉樹。
延伸閱讀:
二、二叉樹重要性質(zhì)
二叉樹中,第m-層非常多有2^(m-1)個結(jié)點(根結(jié)點為名列前茅層)高度為k的二叉樹至多有2^k-1個結(jié)點二叉樹T葉子結(jié)點總數(shù)為n0,度為2的結(jié)點個數(shù)為n2,則n0=n2+1如果完全二叉樹有n個結(jié)點,那么樹較高為log2(n)+1對于完全二叉樹,從上至下,從左至右對每個結(jié)點從1-n編號,那么對于結(jié)點n有:如果i=1,那么此結(jié)點為根結(jié)點,如果i>1那么該結(jié)點的父結(jié)點為不大于i/2的最大整數(shù)如果2*i>n,那么i結(jié)點沒有左子樹,如果2*i<=n那么該結(jié)點的左子樹編號為2*i如果2*i+1>n,那么結(jié)點i沒有右子樹,如果2*i+1<=n那么該結(jié)點的右子樹編號為2*i+1