题目描述
给定以两个序列,分别为先序序列和中序序列,求后序序列
假定一棵二叉树的每个结点都用一个大写字母描述。且输入的字符串的长度不超过26
输入样例
ABC
BAC
FDXEAG
XDEFAG
输出样例
BCA
XEDGAF
思路
主要就是弄清楚边界问题,下面的边界问题自己好好体会一下
假设节点数为:n,根节点在中序遍历中下标是x(从0开始), 那么
左子树在中序遍历中的区间段就是:[0, x), 右子树在中序遍历中的区间段就是:(x, n - 1];
左子树在前序遍历中的区间段就是:[1, 1 + x), 右子树在前序遍历中的区间段就是:[1 + x, n - 1];
C代码
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define MaxSize 26
//定义树结点的结构
typedef struct BiTNode {
char data;
struct BiTNode* lchild, * rchild;
}BiTNode,*BiTree;
/*
里面的参数分别是
先序数组,先序左端点(左子树开始的下标),先序右端点(左子树结束的下标),
中序数组,中序左端点(右子树开始的下标),中序右端点(左子树结束的下标)
*/
BiTree CreatTree(char* preorder, int pl, int pr, char* inorder, int il, int ir) {
BiTNode* curRoot = (BiTNode*)calloc(1, sizeof(BiTNode));//当前根结点
curRoot->data = preorder[pl];
int leftLength, rigthLength;//左右子树的结点的个数
leftLength = rigthLength = 0;
int i;
//找到当前根结点在中序序列中的下标
for (i = il; inorder[i] != curRoot->data; i++);
leftLength = i - il;
rigthLength = ir - i;
if (leftLength)
{
//如果左子树不为空,则递归建立左子树
curRoot->lchild = CreatTree(preorder, pl + 1, pl + leftLength, inorder, il, il + leftLength - 1);
}
else
{
curRoot->lchild = NULL;
}
if (rigthLength)
{
//如果右子树不为空,则递归建立右子树
curRoot->rchild = CreatTree(preorder, pr - rigthLength + 1, pr, inorder, ir - rigthLength + 1, ir);
}
else
{
curRoot->rchild = NULL;
}
return curRoot;
}
BiTree buildTree(char* preorder, int preorder_size, char* inorder, int inorder_size) {
BiTNode* root = (BiTNode*)calloc(1, sizeof(BiTNode));
root = NULL;//这一步是必须要有的,自己好好体会
if (preorder_size < 1)
{
return root;//表示空树
}
else
{
return CreatTree(preorder, 0, preorder_size - 1, inorder, 0, inorder_size - 1);
}
}
//后序遍历
void PostOrder(BiTree root) {
if (root)
{
PostOrder(root->lchild);
PostOrder(root->rchild);
printf("%c", root->data);
}
}
int main() {
char preorder[MaxSize];//先序序列
char inorder[MaxSize];//中序序列
BiTree root;
while (~scanf("%s%s",preorder,inorder))//等价于scanf("%s%s",preorder,inorder)!=EOF
{
int preorder_size = strlen(preorder);
int inorder_size = strlen(inorder);
root = buildTree(preorder, preorder_size, inorder, inorder_size);
PostOrder(root);
printf("\n");
}
return 0;
}