用C语言编写的程序,该程序能够从键盘接收字符输入,并以此构建一个深度不小于3的二叉树(采用二叉链表存储结构)。之后,程序会执行先序、中序和后序遍历,统计节点总数,计算二叉树的深度,并统计叶子节点的数量。
时间: 2024-11-15 16:24:00 浏览: 1
头歌数据结构二叉树的二叉链表存储及基本操作
5星 · 资源好评率100%
在C语言中,编写这样的程序需要以下几个步骤:
1. **定义二叉链表结构**:首先创建一个二叉链表节点结构体,包含指向左右孩子的指针和存储字符的数据。
```c
typedef struct Node {
char data;
struct Node* left;
struct Node* right;
} Node;
```
2. **获取用户输入并构建二叉树**:通过循环从键盘读取字符,然后插入到二叉树中。这里可以递归地添加新节点,左孩子对应字符ASCII值小于当前节点,右孩子反之。
```c
void insertNode(Node** root, char ch) {
if (*root == NULL) {
*root = (Node*)malloc(sizeof(Node));
(*root)->data = ch;
(*root)->left = (*root)->right = NULL;
} else if (ch < (*root)->data) {
insertNode(&((*root)->left), ch);
} else {
insertNode(&((*root)->right), ch);
}
}
```
3. **遍历和统计**:
- 先序遍历(根-左-右):从根开始,递归地访问左子树,然后访问当前节点,最后访问右子树。
- 中序遍历(左-根-右):从左子树开始,访问当前节点,然后递归地访问右子树。
- 后序遍历(左-右-根):类似先序,但最后访问根节点。
```c
void preOrder(Node* node) {
if (node != NULL) {
printf("%c ", node->data);
preOrder(node->left);
preOrder(node->right);
}
}
// 中序和后序遍历类似,只需调整递归顺序
```
4. **计算深度和叶子节点数**:使用递归来计算最大深度,如果节点为空则返回0;非空节点的最大深度等于左右子树的深度加1。同时,在遍历时检查每个节点是否为叶子节点(无子节点),累加计数。
```c
int maxDepth(Node* node) {
if (node == NULL) return 0;
int leftDepth = maxDepth(node->left);
int rightDepth = maxDepth(node->right);
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
int countLeaves(Node* node) {
if (node == NULL || (node->left == NULL && node->right == NULL)) return 1;
return countLeaves(node->left) + countLeaves(node->right);
}
```
5. **主函数**:将上述部分整合在一起,让用户输入字符,构建树,然后执行遍历和计算。
```c
int main() {
// 获取输入并构建树
Node* root = NULL;
// ...
// 打印遍历结果
printf("Preorder traversal: ");
preOrder(root);
printf("\nInorder traversal: ");
inOrder(root); // 类似preOrder,假设有一个inOrder函数
printf("\nPostorder traversal: ");
postOrder(root); // 类似preOrder,假设有一个postOrder函数
// 计算深度和叶子节点数
int depth = maxDepth(root);
int leafCount = countLeaves(root);
printf("\nDepth: %d\nLeaf nodes: %d\n", depth, leafCount);
return 0;
}
```
阅读全文