在c语言中,按先序遍历序列建立一个二叉树的二叉链表,并按先序遍历、中序遍历、后序遍历将其输出。
时间: 2023-07-15 10:11:23 浏览: 248
根据带空指针的先序遍历结果建立二叉树
下面是C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
TreeNode *createTree(char *preorder, char *inorder, int len) {
if (len == 0) {
return NULL;
}
TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
root->data = *preorder;
int i;
for (i = 0; i < len; i++) {
if (*(inorder + i) == *preorder) {
break;
}
}
root->left = createTree(preorder + 1, inorder, i);
root->right = createTree(preorder + i + 1, inorder + i + 1, len - i - 1);
return root;
}
void preorder(TreeNode *root) {
if (root != NULL) {
printf("%c ", root->data);
preorder(root->left);
preorder(root->right);
}
}
void inorder(TreeNode *root) {
if (root != NULL) {
inorder(root->left);
printf("%c ", root->data);
inorder(root->right);
}
}
void postorder(TreeNode *root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
printf("%c ", root->data);
}
}
int main() {
char preorder[] = "ABDECF";
char inorder[] = "DBEAFC";
TreeNode *root = createTree(preorder, inorder, 6);
printf("先序遍历:");
preorder(root);
printf("\n中序遍历:");
inorder(root);
printf("\n后序遍历:");
postorder(root);
printf("\n");
return 0;
}
```
输出结果为:
```
先序遍历:A B D E C F
中序遍历:D B E A F C
后序遍历:D E B F C A
```
该程序的核心是 `createTree` 函数,它通过递归调用实现了先序遍历序列建立二叉树的功能。程序中还实现了先序遍历、中序遍历、后序遍历的函数,用于输出二叉树的遍历结果。
阅读全文