假设二叉树中每个结点值为单个字符，采用二叉链存储结构存储。设计一个算法计算一颗给定二叉树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);
}

相关问题

假设二叉树中的每个结点值为单个字符，采用二叉链存储结构存储。设计一个算法，计算一棵给定二叉树b中的所有单分支结点个数。

可以轻易地想到一个递归算法：

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 加上单分支节点的子树中的单分支节点个数；如果不是，就分别递归遍历它的左右子树，并将它们的结果相加。

当然也可以使用栈或队列来实现非递归的遍历算法，这里就不再赘述。

假设二叉树中的每个结点值 为单个字符，采用二叉链存储结构存储，设计一个算法，计算一棵给定二叉树b中的所有单分支结点个数 用C语言

好的，我来回答你的问题。

算法如下：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树结构体
typedef struct BiTNode {
    char data;  // 数据域
    struct BiTNode *lchild, *rchild;  // 左右孩子指针
} BiTNode, *BiTree;

// 计算单分支结点个数
int CountSingleBranchNode(BiTree T) {
    if (T == NULL) {
        return 0;
    }
    if (T->lchild == NULL && T->rchild == NULL) {
        // 叶子结点
        return 0;
    } else if (T->lchild == NULL) {
        // 只有右子树
        return 1 + CountSingleBranchNode(T->rchild);
    } else if (T->rchild == NULL) {
        // 只有左子树
        return 1 + CountSingleBranchNode(T->lchild);
    } else {
        // 左右子树都有
        return CountSingleBranchNode(T->lchild) + CountSingleBranchNode(T->rchild);
    }
}

int main() {
    // 构造二叉树
    BiTree T = (BiTree)malloc(sizeof(BiTNode));
    T->data = 'A';
    T->lchild = (BiTree)malloc(sizeof(BiTNode));
    T->lchild->data = 'B';
    T->lchild->lchild = (BiTree)malloc(sizeof(BiTNode));
    T->lchild->lchild->data = 'D';
    T->lchild->lchild->lchild = NULL;
    T->lchild->lchild->rchild = NULL;
    T->lchild->rchild = NULL;
    T->rchild = (BiTree)malloc(sizeof(BiTNode));
    T->rchild->data = 'C';
    T->rchild->lchild = (BiTree)malloc(sizeof(BiTNode));
    T->rchild->lchild->data = 'E';
    T->rchild->lchild->lchild = NULL;
    T->rchild->lchild->rchild = (BiTree)malloc(sizeof(BiTNode));
    T->rchild->lchild->rchild->data = 'G';
    T->rchild->lchild->rchild->lchild = NULL;
    T->rchild->lchild->rchild->rchild = NULL;
    T->rchild->rchild = (BiTree)malloc(sizeof(BiTNode));
    T->rchild->rchild->data = 'F';
    T->rchild->rchild->lchild = NULL;
    T->rchild->rchild->rchild = NULL;

    // 计算单分支结点个数
    int count = CountSingleBranchNode(T);

    // 输出结果
    printf("单分支结点个数为：%d\n", count);

    return 0;
}

这个算法的思路是：先判断当前结点是否为叶子结点，如果是，则返回0；如果不是，则判断左右子树是否存在。如果只有左子树或只有右子树，则返回1加上对应子树的单分支结点个数；如果左右子树都存在，则返回左右子树的单分支结点个数之和。

以上是用 C 语言实现的算法，希望能够帮助到你。