统计二叉树的叶结点个数 c

统计二叉树（也称为满二叉树或完全二叉树）的叶子节点个数可以通过公式计算，对于深度为n的完全二叉树，其叶子节点数等于2^(n-1)。这是因为在一个完整的二叉树中，除了最后一层可能不满，其余每一层都是满的，且最后一层的叶子节点从左到右排列。

例如，一个深度为3的完全二叉树有8个节点，其中4个是叶子节点（即深度为0和1的节点）。如果是高度未知的二叉树，你可以采用递归的方式来遍历所有节点并计数：

1. 如果当前节点为空，则返回0。
2. 如果当前节点非空，如果它是叶子节点则计数加一，然后分别对左右子节点递归调用此方法。
3. 返回叶子节点总数。

以下是简单的C语言伪代码表示：

int countLeaves(Node* root) {
    if (root == NULL) return 0;
    if (!root->left && !root->right) // 叶子节点
        return 1;
    else
        return countLeaves(root->left) + countLeaves(root->right);
}

如果你有一个具体的二叉树实例，可以先将其转换为完全二叉树，然后再按照上述方法计算叶子节点数。

相关问题

在C语言的环境下，用递归的方法实现以下算法，以二叉链表表示二叉树，建立一棵二叉树，输出二叉树的先序、中序和后序遍历结果，计算二叉树的深度，统计二叉树的结点个数，统计二叉树的叶结点个数，统计二叉树的度为1的结点个数，输出二叉树中从每个叶子结点到根结点的路径。

你的问题是：在 C 语言中使用递归实现二叉树的各种操作以及路径输出。

好的，让我来回答你的问题。下面是递归实现的一些函数，可以用于建立二叉树、遍历二叉树、计算二叉树深度、统计节点数、统计叶节点数、统计度为1的节点数，并输出根节点到叶节点的路径。

首先，定义二叉树节点的结构体：

typedef struct binary_tree_node {
    int value;
    struct binary_tree_node* left;
    struct binary_tree_node* right;
} BinaryTreeNode;

接下来，是递归实现的函数：

1. 建立二叉树

BinaryTreeNode* create_binary_tree() {
    int value;
    printf("请输入节点值（-1表示空节点）：");
    scanf("%d", &value);
    if (value == -1) {
        return NULL;
    }
    BinaryTreeNode* node = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
    node->value = value;
    printf("请输入 %d 的左子树：\n", value);
    node->left = create_binary_tree();
    printf("请输入 %d 的右子树：\n", value);
    node->right = create_binary_tree();
    return node;
}

2. 先序遍历

void preorder_traversal(BinaryTreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->value);
    preorder_traversal(root->left);
    preorder_traversal(root->right);
}

3. 中序遍历

void inorder_traversal(BinaryTreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorder_traversal(root->left);
    printf("%d ", root->value);
    inorder_traversal(root->right);
}

4. 后序遍历

void postorder_traversal(BinaryTreeNode* root) {
    if (root == NULL) {
        return;
    }
    postorder_traversal(root->left);
    postorder_traversal(root->right);
    printf("%d ", root->value);
}

5. 计算二叉树深度

int binary_tree_depth(BinaryTreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int left_depth = binary_tree_depth(root->left);
    int right_depth = binary_tree_depth(root->right);
    return (left_depth > right_depth ? left_depth : right_depth) + 1;
}

6. 统计节点数

int count_nodes(BinaryTreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    return count_nodes(root->left) + count_nodes(root->right) + 1;
}

7. 统计叶节点数

int count_leaf_nodes(BinaryTreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return count_leaf_nodes(root->left) + count_leaf_nodes(root->right);
}

8. 统计度为1的节点数

int count_degree_1_nodes(BinaryTreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int degree = 0;
    if (root->left != NULL) {
        degree++;
    }
    if (root->right != NULL) {
        degree++;
    }
    return degree == 1 ? 1 + count_degree_1_nodes(root->left) + count_degree_1_nodes(root->right) : 
                         count_degree_1_nodes(root->left) + count_degree_1_nodes(root->right);
    
}

9. 输出根节点到叶节点的路径

void print_path(BinaryTreeNode* root, int* path, int top) {
    if (root == NULL) {
        return;
    }
    path[top++] = root->value;
    if (root->left == NULL && root->right == NULL) {
        printf("路径：");
        for (int i = 0; i < top; i++) {
            printf("%d ", path[i]);
        }
        printf("\n");
    } else {
        print_path(root->left, path, top);
        print_path(root->right, path, top);
    }
}

至此，递归实现的二叉树函数已经完成。

在c语言中用递归的方法实现以下算法：1.以二叉链表表示二叉树，建立一棵二叉树；2.输出二叉树的先序、中序和后序遍历结果；3.计算二叉树的深度；4.统计二叉树的结点个数； 5.统计二叉树的叶结点个数；6.统计二叉树的度为1的结点个数；

1. 以二叉链表表示二叉树，建立一棵二叉树的递归实现方法如下：

typedef struct BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void CreateBiTree(BiTree *T) {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') {
        *T = NULL;
    } else {
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = ch;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
}

2. 输出二叉树的先序、中序和后序遍历结果的递归实现方法如下：

void PreOrderTraverse(BiTree T) {
    if (T) {
        printf("%c ", T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}

void InOrderTraverse(BiTree T) {
    if (T) {
        InOrderTraverse(T->lchild);
        printf("%c ", T->data);
        InOrderTraverse(T->rchild);
    }
}

void PostOrderTraverse(BiTree T) {
    if (T) {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        printf("%c ", T->data);
    }
}

3. 计算二叉树的深度的递归实现方法如下：

int TreeDepth(BiTree T) {
    if (!T) {
        return 0;
    } else {
        int leftDepth = TreeDepth(T->lchild);
        int rightDepth = TreeDepth(T->rchild);
        return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
    }
}

4. 统计二叉树的结点个数的递归实现方法如下：

int NodeCount(BiTree T) {
    if (!T) {
        return 0;
    } else {
        return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
    }
}

5. 统计二叉树的叶结点个数的递归实现方法如下：

int LeafCount(BiTree T) {
    if (!T) {
        return 0;
    } else if (!T->lchild && !T->rchild) {
        return 1;
    } else {
        return LeafCount(T->lchild) + LeafCount(T->rchild);
    }
}

6. 统计二叉树的度为1的结点个数的递归实现方法如下：

int DegreeOneCount(BiTree T) {
    if (!T) {
        return 0;
    } else if ((!T->lchild && T->rchild) || (T->lchild && !T->rchild)) {
        return DegreeOneCount(T->lchild) + DegreeOneCount(T->rchild) + 1;
    } else {
        return DegreeOneCount(T->lchild) + DegreeOneCount(T->rchild);
    }
}