葉子結點

葉子結點

葉子結點是離散數學中的概念。一棵樹當中沒有子結點（即度為0）的結點稱為葉子結點，簡稱“葉子”。葉子是指度為0的結點，又稱為終端結點。

目錄

1概念含義 2例題 3計算方式

概念含義

葉子結點

葉子結點

葉子結點就是度為0的結點就是沒有子結點的結點

n：度為0的結點數，n:度為1的結點 n：度為2的結點數。 N是總結點

在二叉樹中：

n=n+1；

N=n+n+n

例題

一棵樹度為4，其中度為1，2，3，4的結點個數分別為4，2，1，1，則這棵樹的葉子節點個數為多少？

解：因為任一棵樹中，結點總數=度數*該度數對應的結點數+1，所以：

n0+4+2+1+1 = （0*n0 + 1*4 + 2*2 + 3*1 + 4*1）+1

則：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;

}

1，該演演算法的代碼模塊的獨立性算是設計的比較好的。

1.1，耦合比較低，傳入樹的樹根，返回樹的葉子節點的個數。

1.2，內聚比較高，模塊中的代碼比較緊密。容易閱讀，易維護。

2，該演演算法是用遞歸實現的，效率肯定不是很高。

3，該演演算法是在對樹的後序遍歷的基礎上實現的。如果該節點的左子樹，再右子樹，

最後是根節點。

目錄