在c语言中,按先序遍历序列建立一个二叉树的二叉链表,并按先序遍历、中序遍历、后序遍历将其输出。输入由用户决定
时间: 2023-07-15 10:11:07 浏览: 162
根据带空指针的先序遍历结果建立二叉树
下面是按照您的要求实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
char data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 先序遍历建立二叉树
TreeNode* createTree() {
char ch;
scanf("%c", &ch);
if (ch == '#') {
return NULL;
}
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = ch;
node->left = createTree();
node->right = createTree();
return node;
}
// 先序遍历
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("请输入先序遍历序列(以#代表空节点):");
TreeNode *root = createTree();
printf("先序遍历结果为:");
preOrder(root);
printf("\n中序遍历结果为:");
inOrder(root);
printf("\n后序遍历结果为:");
postOrder(root);
printf("\n");
return 0;
}
```
在程序中,我们先定义了一个二叉树节点的结构体,包含数据、左子树和右子树三个成员;然后,通过递归的方式按照先序遍历序列构建了一个二叉树,其中 # 表示空节点;最后,分别实现了先序遍历、中序遍历和后序遍历,并输出了遍历结果。在程序运行时,用户需要输入先序遍历序列。
阅读全文