用C语言建立一棵用二叉链表方式存储的二叉树,并实现对其进行先序、中序、后序三种方法遍历,输出遍历结果。
时间: 2024-02-06 15:10:20 浏览: 77
好的,以下是用C语言实现建立二叉树和三种遍历的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点结构体
typedef struct TreeNode {
char data; // 结点存储数据
struct TreeNode *left; // 左子树指针
struct TreeNode *right; // 右子树指针
} TreeNode;
// 建立二叉树函数
TreeNode* create_tree() {
TreeNode *p;
char ch;
scanf("%c", &ch); // 读入一个字符
if (ch == '#') { // 如果是#,表示该结点为空
p = NULL;
} else {
// 创建一个新结点
p = (TreeNode*)malloc(sizeof(TreeNode));
p->data = ch;
// 递归创建左右子树
p->left = create_tree();
p->right = create_tree();
}
return p;
}
// 先序遍历函数
void preorder(TreeNode *root) {
if (root == NULL) {
return;
}
printf("%c ", root->data);
preorder(root->left);
preorder(root->right);
}
// 中序遍历函数
void inorder(TreeNode *root) {
if (root == NULL) {
return;
}
inorder(root->left);
printf("%c ", root->data);
inorder(root->right);
}
// 后序遍历函数
void postorder(TreeNode *root) {
if (root == NULL) {
return;
}
postorder(root->left);
postorder(root->right);
printf("%c ", root->data);
}
int main() {
printf("请输入二叉树的结点,空结点用#表示:\n");
TreeNode *root = create_tree();
printf("\n先序遍历结果为:");
preorder(root);
printf("\n中序遍历结果为:");
inorder(root);
printf("\n后序遍历结果为:");
postorder(root);
printf("\n");
return 0;
}
```
这里我们采用先序遍历读入二叉树的结点,其中`#`表示空结点。然后我们实现了三个遍历函数,分别输出先序、中序、后序的遍历结果。最后在`main()`函数中,我们依次调用创建二叉树和三种遍历函数即可。
阅读全文