假设二叉树中的每个结点值为单个字符,采用二叉链存储结构存储。设计一个算法,计算一棵给定二叉树b中的所有单分支结点个数。
时间: 2024-05-02 11:19:14 浏览: 18
可以轻易地想到一个递归算法:
```python
def count_single_branch_nodes(root):
if root is None:
return 0
if root.left is None and root.right is not None:
return 1 + count_single_branch_nodes(root.right)
if root.left is not None and root.right is None:
return 1 + count_single_branch_nodes(root.left)
return count_single_branch_nodes(root.left) + count_single_branch_nodes(root.right)
```
这个算法首先判断当前节点是不是单分支节点,如果是的话,就返回 1 加上单分支节点的子树中的单分支节点个数;如果不是,就分别递归遍历它的左右子树,并将它们的结果相加。
当然也可以使用栈或队列来实现非递归的遍历算法,这里就不再赘述。
相关问题
假设二叉树中每个结点值为单个字符,采用二叉链存储结构存储设计,一个算法计算一棵树给定二叉树BT中的所有单分支结点个数
好的,针对你的问题,我来给出一个算法:
1. 定义一个计数器count,用来记录单分支结点的个数。
2. 从根节点开始,如果当前节点是空节点,则直接返回0。
3. 如果当前节点只有左儿子或者只有右儿子,则将计数器count加1。
4. 分别递归遍历当前节点的左子树和右子树,将递归结果相加并返回。
5. 最终返回count的值即可。
下面是该算法的Python代码实现:
```python
def count_single_branch_nodes(root):
if not root:
return 0
count = 0
if root.left and not root.right:
count += 1
elif root.right and not root.left:
count += 1
count += count_single_branch_nodes(root.left) + count_single_branch_nodes(root.right)
return count
```
这个算法的时间复杂度是O(n),其中n是二叉树中节点的数量。
假设二叉树中每个结点值为单个字符,采用二叉链存储结构存储。设计一个算法计算一颗给定二叉树b中的所有双分支结点个数。
算法步骤如下:
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);
}