二叉树的中序序列和后序序列来求前序序列的代码,用c语言来实现。
时间: 2023-11-24 19:07:12 浏览: 34
以下是用C语言实现根据中序遍历和后序遍历求前序遍历的代码:
```c
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 1000
// 二叉树结点
typedef struct Node {
char data;
struct Node* lchild;
struct Node* rchild;
} Node, *pNode;
// 根据中序遍历和后序遍历构建二叉树
pNode buildTree(char* inOrder, char* postOrder, int len) {
if (len <= 0) return NULL;
pNode root = (pNode)malloc(sizeof(Node));
root->data = postOrder[len-1];
int i;
for (i = 0; i < len; i++) {
if (inOrder[i] == root->data) break;
}
root->lchild = buildTree(inOrder, postOrder, i);
root->rchild = buildTree(inOrder+i+1, postOrder+i, len-i-1);
return root;
}
// 前序遍历
void preOrder(pNode root) {
if (root == NULL) return;
printf("%c ", root->data);
preOrder(root->lchild);
preOrder(root->rchild);
}
int main() {
char inOrder[MAXSIZE], postOrder[MAXSIZE];
printf("请输入中序序列:");
scanf("%s", inOrder);
printf("请输入后序序列:");
scanf("%s", postOrder);
int len = strlen(inOrder);
pNode root = buildTree(inOrder, postOrder, len);
printf("前序遍历结果为:");
preOrder(root);
printf("\n");
return 0;
}
```
对于输入的中序序列和后序序列,程序会构建出一棵二叉树,并输出其前序遍历序列。