1. 首页 > 经验  > 正文

叶子结点

叶子结点

叶子结点是离散数学中的概念。一棵树当中没有子结点(即度为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,所以:
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,该算法是在对树的后序遍历的基础上实现的。如果该节点的左子树,再右子树,最后是根节点。

本文由'长星小娘子'发布,不代表演示站立场,转载/删除联系作者,如需删除请-> 关于侵权处理说明