给定先序序列,按照该序列创建二叉树,并输出它对应的先序序列、中序序列和后序序列。用c语言实现代码。
时间: 2023-12-08 22:56:50 浏览: 74
二叉树的前序,中序,后序排列C语言程序
可以使用递归的方法,每次递归的时候取出先序序列的第一个元素作为当前的根节点,然后根据根节点将中序序列分成左子树和右子树两部分,再递归创建左右子树,最后输出先序、中序和后序序列即可。
下面是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 树的结构体
typedef struct TreeNode {
char val;
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->val = preorder[0];
root->left = NULL;
root->right = NULL;
int i;
// 在中序序列中查找根节点的位置
for (i = 0; i < len; i++) {
if (inorder[i] == preorder[0]) break;
}
// 递归创建左右子树
root->left = createTree(preorder + 1, inorder, i);
root->right = createTree(preorder + i + 1, inorder + i + 1, len - i - 1);
return root;
}
// 先序遍历
void preorderTraversal(TreeNode* root) {
if (root == NULL) return;
printf("%c ", root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 中序遍历
void inorderTraversal(TreeNode* root) {
if (root == NULL) return;
inorderTraversal(root->left);
printf("%c ", root->val);
inorderTraversal(root->right);
}
// 后序遍历
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%c ", root->val);
}
int main() {
char preorder[] = {'A', 'B', 'D', 'E', 'C', 'F', 'G'};
char inorder[] = {'D', 'B', 'E', 'A', 'F', 'C', 'G'};
int len = sizeof(preorder) / sizeof(char);
TreeNode* root = createTree(preorder, inorder, len);
printf("先序遍历:");
preorderTraversal(root);
printf("\n");
printf("中序遍历:");
inorderTraversal(root);
printf("\n");
printf("后序遍历:");
postorderTraversal(root);
printf("\n");
return 0;
}
```
输出结果为:
```
先序遍历:A B D E C F G
中序遍历:D B E A F C G
后序遍历:D E B F G C A
```
注意:这里假设了先序序列和中序序列中的每个元素都不相同,否则就无法确定根节点在中序序列中的位置了。如果存在相同元素,可以加入一个计数器来记录先序序列中根节点的位置。
阅读全文