一、求结点总数
1.使用1个局部变量进行计数
有的方法中将左右子树分别进行计算,需要使用到两个变量;若使用全局变量,在对多个二叉树计算节点数时结果会进行累计,不易观察,使用一个全局变量就很方便。
2.思想
结点总数=根结点数+左子树结点数+右结点数;判断根结点不为空,count++,然后再加上左右子树的个数。
3.注意
这里计算的是结点总数,左右子树需要分别进行判断是否为空。
4.代码
//总的结点数
int NodeNum(BTNode *T)
{
int count=0;
if (T)
{
count++;
if (T->Lchild)
{
count+= NodeNum(T->Lchild);
}
if (T->Rchild)
{
count+= NodeNum(T->Rchild);
}
return count;
}
}
二、求叶子结点总数
1、与计算总结点数的区别
这里需要注意叶子结点的定义,即左孩子和右孩子同时为空,同时也需要同时判断左子树以及右子树。
2、代码
//叶子结点数
int LeavesNodeNum(BTNode* T)
{
int count = 0;
if (T != NULL)
{
if ((T->Lchild == NULL) && (T->Rchild == NULL)) count++;
count+=LeavesNodeNum(T->Lchild);
count+=LeavesNodeNum(T->Rchild);
}
return count;
}
三、运行结果
用二叉链表的先序遍历法建立二叉树,下图是进行测试的二叉树:
运行结果如下: 文章来源:https://www.toymoban.com/news/detail-757541.html
文章来源地址https://www.toymoban.com/news/detail-757541.html
到了这里,关于递归求二叉树的结点总数及叶子结点总数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!