首页假设二叉树采用二叉链表存储结构，试设计一个算法求二叉树的叶子结点数（用c++和c语言实现代码）

假设二叉树采用二叉链表存储结构，试设计一个算法求二叉树的叶子结点数（用c++和c语言实现代码）

时间: 2025-06-14 08:16:32 浏览: 21

在二叉链表存储结构中，每个节点通常包含两个指针，分别指向左子节点和右子节点。为了计算二叉树的叶子节点（即没有子节点的节点），你可以遍历整个树并检查每个节点是否为叶子。这里给出C++和C语言的简单示例： **C++实现：** ```cpp #include <iostream> struct Node { int data; Node* left; Node* right; }; int countLeaves(Node* root) { if (root == nullptr) return 0; // 如果当前节点是叶子节点，计数加一 if (root->left == nullptr && root->right == nullptr) return 1; // 递归地计算左右子树的叶子节点数，然后相加 return countLeaves(root->left) + countLeaves(root->right); } // 示例用法 int main() { // 创建一个二叉树，并设置叶子节点... // ... int leafCount = countLeaves(root); // 计算叶子节点总数 std::cout << "Number of leaves: " << leafCount << std::endl; return 0; } ``` **C语言实现：** ```c #include <stdio.h> typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; int countLeaves(TreeNode* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 1; return countLeaves(root->left) + countLeaves(root->right); } // 示例用法 int main() { // 初始化一个二叉树... TreeNode* root = ...; int leafCount = countLeaves(root); // 计算叶子节点数 printf("Number of leaves: %d\n", leafCount); return 0; } ``` 这两个函数都是通过递归的方式遍历二叉树，直到遇到叶子节点为止。

阅读全文