用C语言编程:按先序遍历序列建立一个二叉树的二叉链表,统计二叉树中叶子结点个数和二叉树的深度。
时间: 2024-01-23 22:43:02 浏览: 82
以下是按照您的要求用C语言编写的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
char data; // 数据域
struct TreeNode *left; // 左子树指针
struct TreeNode *right; // 右子树指针
} TreeNode, *TreeNodePtr;
// 先序遍历序列建立二叉树
TreeNodePtr createBinaryTree(char *preorder, int *index) {
char data = preorder[(*index)++];
if (data == '#') {
return NULL;
}
TreeNodePtr node = (TreeNodePtr)malloc(sizeof(TreeNode));
node->data = data;
node->left = createBinaryTree(preorder, index);
node->right = createBinaryTree(preorder, index);
return node;
}
// 统计叶子结点个数
int countLeafNodes(TreeNodePtr root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return countLeafNodes(root->left) + countLeafNodes(root->right);
}
// 计算二叉树深度
int getTreeDepth(TreeNodePtr root) {
if (root == NULL) {
return 0;
}
int leftDepth = getTreeDepth(root->left);
int rightDepth = getTreeDepth(root->right);
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
// 主函数
int main() {
char preorder[100] = "ABD##E##CF##G##";
int index = 0;
TreeNodePtr root = createBinaryTree(preorder, &index);
printf("叶子结点个数为:%d\n", countLeafNodes(root));
printf("二叉树深度为:%d\n", getTreeDepth(root));
return 0;
}
```
代码的思路是先用先序遍历序列构建二叉树,然后分别计算叶子结点个数和二叉树的深度。其中,`createBinaryTree`函数用于构建二叉树,`countLeafNodes`函数用于计算叶子结点个数,`getTreeDepth`函数用于计算二叉树深度。在主函数中,我们先使用给定的先序遍历序列构建二叉树,然后调用`countLeafNodes`和`getTreeDepth`函数来计算叶子结点个数和二叉树深度,并输出结果。
阅读全文