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

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

*  题目描述

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

*  输入

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

*  输出

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

*  样例输入

ABC
    BAC
    FDXEAG
    XDEFAG

*  样例输出

BCA
    XEDGAF

*  代码

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    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;
    }

*  总结

注意递归跳出条件
    注意树的分配空间的时候，一定要防止断链
    注意递归的使用条件