C语言实现先序中序还原二叉树

Question

问题遇到的现象和发生背景

C语言实现先序中序还原二叉树

问题相关代码，请勿粘贴截图

这是我写的关于二叉树的建立和遍历，但是对于先序和中序还原一窍不通，希望能给出详细代码和注释

#include<stdio.h>
#include<stdlib.h>
typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void PreOrderTraverse(BiTree T)//二叉树的先序遍历
{
    if(T==NULL)
        return ;
    printf("%c ",T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}
void InOrderTraverse(BiTree T)//二叉树的中序遍历
{
   if(T==NULL)
       return ;
   InOrderTraverse(T->lchild);
    printf("%c ",T->data);
   InOrderTraverse(T->rchild);
}
void PostOrderTraverse(BiTree T)//后序遍历
{
    if(T==NULL)
        return;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c ",T->data);
}
//求树的深度
int TreeDeep(BiTree T)
 {
    int deep = 0;
    if (T != NULL)
     {
        int leftDeep = TreeDeep(T->lchild);
        int rightDeep = TreeDeep(T->rchild);
        deep = leftDeep >= rightDeep ? leftDeep + 1 : rightDeep + 1;
    }
    return deep;
}
//求树叶的个数
int LeafCount(BiTree T, int &num) 
{
    if (T) 
    {
        if (T->lchild == NULL && T->rchild == NULL)
         {
            num++;
        }
        LeafCount(T->lchild, num);
        LeafCount(T->rchild, num);
    }
    return num;
}
void CreateBiTree(BiTree *T)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')
        *T=NULL;
    else
    {
        *T=(BiTree  )malloc(sizeof(BiTNode));
        if(!*T)
            exit(-1);
        (*T)->data=ch;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
}

int main()
{
    BiTree T;
    int num=0;
    printf("建立二叉树：\n");
    CreateBiTree(&T);
    printf("先序遍历：\n"); 
    PreOrderTraverse (T);
    printf("\n中序遍历：\n"); 
    InOrderTraverse(T);
    printf("\n后序遍历：\n");
    PostOrderTraverse(T);
    printf("\n该二叉树的深度为:");
    printf("%d\n", TreeDeep(T));
    printf("\n该二叉树的叶子结点个数为:");
    printf("%d\n", LeafCount(T, num));
    return 0;
}
假定
先序序列："ABDGHCEIF";
中序序列："GDHBAEICF"; 
如何还原

运行结果及报错内容

我的解答思路和尝试过的方法

这是我们书上关于还原的算法，但是看不懂，不知道在主程序中怎么用
比如 printf("先序遍历：\n");
PreOrderTraverse (T);
可以在主函数中调用，但是还原的函数怎么用呢？

void ReBiTree(char preod[],char inod[],int n,BiTree root)/*恢复函数*/ 
{
    if(n<=0)
    root=NULL;
    else
    PreInOd(preod,inod,1,n,1,n,&root);
}
void PreInOd(char preod[],char inod[],int i,int j,int k,int h,BiTree *t)
{
    *t=(BiTNode *)malloc(sizeof(BiTNode));
    *t->data=preod[i];
    m=k;
    while(inod[m]!=preod[i])
    m++;    
    if(m==k)
    *t->lchild=NULL
    else
    PreInOd(preod,inod,i+1,i+m-k,k,m-1,&t->lchild);
    if(m==h)
    *t->rchild=NULL
    else
    PreInOd(preod,inod,i+m-k+1,j,m+1,h,&t->rchild);
}

我想要达到的结果

希望能完成还原的功能要求，需要尽快给出！也可以不用我上面给的还原代码，但是麻烦能让你给的代码在我给的第一个代码上能运行，多谢！完成后可给报酬！

Answer 1

你题目的解答代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void PreOrderTraverse(BiTree T)//二叉树的先序遍历
{
    if(T==NULL)
        return ;
    printf("%c ",T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}
void InOrderTraverse(BiTree T)//二叉树的中序遍历
{
   if(T==NULL)
       return ;
   InOrderTraverse(T->lchild);
    printf("%c ",T->data);
   InOrderTraverse(T->rchild);
}
void PostOrderTraverse(BiTree T)//后序遍历
{
    if(T==NULL)
        return;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c ",T->data);
}
//求树的深度
int TreeDeep(BiTree T)
 {
    int deep = 0;
    if (T != NULL)
     {
        int leftDeep = TreeDeep(T->lchild);
        int rightDeep = TreeDeep(T->rchild);
        deep = leftDeep >= rightDeep ? leftDeep + 1 : rightDeep + 1;
    }
    return deep;
}
//求树叶的个数
int LeafCount(BiTree T, int &num)
{
    if (T)
    {
        if (T->lchild == NULL && T->rchild == NULL)
         {
            num++;
        }
        LeafCount(T->lchild, num);
        LeafCount(T->rchild, num);
    }
    return num;
}
void CreateBiTree(BiTree *T)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')
        *T=NULL;
    else
    {
        *T=(BiTree  )malloc(sizeof(BiTNode));
        if(!*T)
            exit(-1);
        (*T)->data=ch;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
}


void PreInOd(char preod[],char inod[],int i,int j,int k,int h,BiTree *t)
{
    *t=(BiTNode *)malloc(sizeof(BiTNode));
    (*t)->data=preod[i];
    int m=k;
    while(inod[m]!=preod[i])
        m++;
    if(m==k)
        (*t)->lchild=NULL;
    else
        PreInOd(preod,inod,i+1,i+m-k,k,m-1,&(*t)->lchild);
    if(m==h)
        (*t)->rchild=NULL;
    else
       PreInOd(preod,inod,i+m-k+1,j,m+1,h,&(*t)->rchild);
}
void ReBiTree(char preod[],char inod[],int n,BiTree *root)/*恢复函数*/
{
    if(n<=0)
        root=NULL;
    else
        PreInOd(preod,inod,0,n-1,0,n-1,root);
}

int main()
{
    BiTree T;
    int num = 0;
    char s1[100];
    char s2[100];
    gets(s1);
    gets(s2);
    int n = strlen(s1);
    ReBiTree(s1,s2,n,&T);
    printf("先序遍历：\n");
    PreOrderTraverse (T);
    printf("\n中序遍历：\n");
    InOrderTraverse(T);
    printf("\n后序遍历：\n");
    PostOrderTraverse(T);
    printf("\n该二叉树的深度为:");
    printf("%d\n", TreeDeep(T));
    printf("\n该二叉树的叶子结点个数为:");
    printf("%d\n", LeafCount(T, num));
    return 0;
}

如有帮助，请点击我的回答下方的【采纳该答案】按钮帮忙采纳下，谢谢!