-
葉子結點
鎖定
- 中文名
- 葉子結點
- 外文名
- leaf node
- 類 別
- 離散數學
- 性 質
- 離散數學術語
葉子結點概念含義
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]
- 參考資料
-
- 1. 如何統計樹葉子結點的數目 .網易博客[引用日期2017-01-17]