结点数和叶子结点数有什么区别吗

发布网友发布时间：2023-08-05 04:47

共1个回答

热心网友时间：2024-12-02 08:31

结点数和叶子结点数的区别：

叶子结点是度为0的结点，简单的说就是一个二叉树任意一个分支上的终端节点。

结点包括叶子结点。

在二叉树中：

n0=n2+1；

N=n0+n1+n2

例题

一棵树度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1，则这棵树的叶子节点个数为多少？

解：因为任一棵树中，结点总数=度数+1，所以：

n0+4+2+1+1 = （n0*0 + 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、该算法的代码模块的独立性算是设计的比较好的。耦合比较底，传入树的树根，返回树的叶子节点的个数。内聚比较高，模块中的代码比较紧密。容易阅读，易维护。

2、该算法是用递归实现的，效率肯定不是很高。

3、该算法是在对树的后序遍历的基础上实现的。如果该节点的左子树，再右子树，

最后是根节点。