首页求一个二叉树所有结点总数和叶子结点总数的算法用c语言

求一个二叉树所有结点总数和叶子结点总数的算法用c语言

时间: 2025-01-20 16:13:19 浏览: 48

以下是一个用C语言实现的算法，用于计算二叉树中所有结点的总数和叶子结点的总数： ```c #include <stdio.h> #include <stdlib.h> // 定义二叉树结点结构 struct TreeNode { int data; struct TreeNode* left; struct TreeNode* right; }; // 创建新结点的函数 struct TreeNode* createNode(int data) { struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode)); newNode->data = data; newNode->left = newNode->right = NULL; return newNode; } // 计算结点总数的递归函数 int countNodes(struct TreeNode* root) { if (root == NULL) return 0; return 1 + countNodes(root->left) + countNodes(root->right); } // 计算叶子结点总数的递归函数 int countLeaves(struct 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() { // 创建示例二叉树 struct TreeNode* root = createNode(1); root->left = createNode(2); root->right = createNode(3); root->left->left = createNode(4); root->left->right = createNode(5); // 计算总数 int totalNodes = countNodes(root); int totalLeaves = countLeaves(root); // 输出结果 printf("二叉树结点总数: %d\n", totalNodes); printf("二叉树叶子结点总数: %d\n", totalLeaves); return 0; } ``` 这个程序包含以下主要部分： 1. 定义二叉树结点结构。 2. 创建新结点的函数 `createNode`。 3. 计算所有结点总数的递归函数 `countNodes`。 4. 计算叶子结点总数的递归函数 `countLeaves`。 5. 主函数中创建一个示例二叉树，并调用上述函数计算结果。这个算法的时间复杂度为 O(n)，其中 n 是二叉树的结点总数，因为每个结点都被访问一次。

阅读全文