二叉树先序遍历中序遍历建立二叉树然后后序遍历

男娘i 2022-06-01 07:24 354阅读 0赞

题目描述

二叉树的前序、中序、后序遍历的定义：前序遍历：对任一子树，先访问跟，然后遍历
其左子树，最后遍历其右子树；中序遍历：对任一子树，先遍历其左子树，然后访问
根，最后遍历其右子树；后序遍历：对任一子树，先遍历其左子树，然后遍历其右子
树，最后访问根。给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定
前序遍历与中序遍历能够唯一确定后序遍历）。
输入

两个字符串，其长度n均小于等于26。
第一行为前序遍历，第二行为中序遍历。
二叉树中的结点名称以大写字母表示：A，B，C….最多26个结点。
输出

输入样例可能有多组，对于每组测试样例，
输出一行，为后序遍历的字符串。
样例输入

ABC
BAC
FDXEAG
XDEFAG
样例输出

BCA
XEDGAF

代码

include

typedef struct Bitree{

char data;
struct Bitree * lchild;
struct Bitree * rchild;

} * BiTree,BiNode;

void CreateBiTree(BiTree T,char preOrder,char inOrder,int preLow,int preHigh,int inLow,int inHigh){

T->lchild = NULL;
T->rchild = NULL;
T->data = preOrder[preLow];
if(preLow == preHigh) return;
int i = inLow;
while(inOrder[i] != preOrder[preLow]) i ++;
if(i - 1 >= inLow){
    T->lchild = (BiTree)malloc(sizeof(BiNode));
    CreateBiTree(T->lchild, preOrder, inOrder, preLow + 1, preLow + i - inLow, inLow, i - 1);
}
if(inHigh >= i + 1){
    T->rchild = (BiTree)malloc(sizeof(BiNode));
    CreateBiTree(T->rchild, preOrder, inOrder, preLow + i - inLow + 1, preHigh, i + 1, inHigh);
}

}
void PreOrder(BiTree T){

if(T != NULL){
    printf("%c",T->data);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
}

}

void InOrder(BiTree T){

if(T != NULL){
    InOrder(T->lchild);
    printf("%c",T->data);
    InOrder(T->rchild);
}

}

void PostOrder(BiTree T){

if(T != NULL){
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    printf("%c",T->data);
}

}

int main(int argc, const char * argv[]) {

char preOrder[26],inOrder[26];
while(scanf("%s", preOrder) != EOF){
    scanf("%s", inOrder);
    int n = strlen(preOrder);
    BiTree T = (BiTree)malloc(sizeof(BiNode));
    T->lchild = NULL;
    T->rchild = NULL;
    CreateBiTree(T, preOrder, inOrder, 0, n - 1, 0, n - 1);
    PostOrder(T);
    printf("\n");
}
return 0;