複製鏈接
請複製以下鏈接發送給好友

葉子結點

鎖定
子結點離散數學中的概念。一棵樹當中沒有子結點(即度為0)的結點稱為葉子結點,簡稱“葉子”。 葉子是指出度為0的結點,又稱為終端結點。
中文名
葉子結點
外文名
leaf node
類    別
離散數學
性    質
離散數學術語

葉子結點概念含義

葉子結點 葉子結點
葉子結點 就是出度為0的結點 就是沒有子結點的結點
n0:出度為0的結點數,n1:度為1的結點 n2:度為2的結點數。 N是總結點
二叉樹中:
n0=n2+1;
N=n0+n1+n2

葉子結點例題

一棵樹度為4,其中度為1,2,3,4的結點個數分別為4,2,1,1,則這棵樹的葉子節點個數為多少?
解:因為任一棵樹中,結點總數=度數*該度數對應的結點數+1,所以:
總結點數=1*4+2*2+3*1+4*1+1=16
葉子結點數=16-4-2-1-1(總節點數-度不為0的個數)=8
則:n0=8
其中:n0表示葉子結點。

葉子結點計算方式

該算法的遞歸形式比較容易實現。
具體的代碼塊如下:
int leaf(BiTree root)
{
static int leaf_count = 0; --->在遞歸調用時只進行一次初始化。
if (NULL != root) {
leaf(root->lchild);//求左子樹的葉子數
leaf(root->rchild);//求右子樹的葉子數
if (root->lchild == NULL
&& root->rchild == NULL)
leaf_count++;
}
return leaf_count;
}
主調用:count=LeafCount_BiTree(root)
1,該算法的代碼模塊的獨立性算是設計的比較好的。
1.1,耦合比較低,傳入樹的樹根,返回樹的葉子節點的個數。
1.2,內聚比較高,模塊中的代碼比較緊密。容易閲讀,易維護。
2,該算法是用遞歸實現的,效率肯定不是很高。
3,該算法是在對樹的後序遍歷的基礎上實現的。如果該節點的左子樹,再右子樹,
最後是根節點 [1] 
參考資料