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

2021年6月22日 7点热度 0条评论 来源: hustfc
  • 题目描述
二叉树的前序、中序、后序遍历的定义: 前序遍历:对任一子树,先访问跟,然后遍历
其左子树,最后遍历其右子树; 中序遍历:对任一子树,先遍历其左子树,然后访问
根,最后遍历其右子树; 后序遍历:对任一子树,先遍历其左子树,然后遍历其右子
树,最后访问根。 给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定
前序遍历与中序遍历能够唯一确定后序遍历)。
  • 输入
两个字符串,其长度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;
}
  • 总结
注意递归跳出条件
注意树的分配空间的时候,一定要防止断链
注意递归的使用条件
    原文作者:hustfc
    原文地址: https://blog.csdn.net/weixin_36372879/article/details/79145100
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。