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