假设二叉树中每个结点值为单个字符,采用二叉链存储结构存储。设计一个算法计算一颗给定二叉树b中的所有双分支结点个数。
时间: 2023-06-05 09:47:19 浏览: 397
设二叉树采用链式存储结构,试设计一个算法计算一颗给定二叉树叶子节点的数目
5星 · 资源好评率100%
算法步骤如下:
1. 判断二叉树b是否为空,若为空则返回。
2. 若二叉树b不为空,则判断当前结点是否为双分支结点,若是则计数器加1。
3. 递归遍历当前结点的左子树和右子树,分别计算左子树和右子树中的双分支结点个数。
4. 返回左子树和右子树中的双分支结点个数之和加上当前结点是否为双分支结点的计数器值。
算法实现如下:
int countDoubleNode(BiTree b) {
if (b == NULL) {
return ;
}
int count = ;
if (b->lchild != NULL && b->rchild != NULL) {
count = 1;
}
return count + countDoubleNode(b->lchild) + countDoubleNode(b->rchild);
}
阅读全文