叶子结点_离散数学术语 - 威林百科weilinceramic.com

叶子结点

离散数学术语

叶子结点是离散数学中的概念。一棵树当中没有子结点（即度为0）的结点称为叶子结点，简称“叶子”。叶子是指出度为0的结点，又称为终端结点。

概念含义

叶子结点就是出度为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，该算法是在对树的后序遍历的基础上实现的。如果该节点的左子树，再右子树，

最后是根节点。

参考资料

最新修订时间：2024-12-18 14:47

条目作者

概述

概念含义

例题

参考资料