Akoasm.z 2022-01-13 00:57 采纳率: 66.7%
浏览 99
已结题

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

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

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);
}
我想要达到的结果

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

  • 写回答

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;
    }
    

    img

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

    img

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 1月22日
  • 已采纳回答 1月14日
  • 修改了问题 1月13日
  • 创建了问题 1月13日

悬赏问题

  • ¥30 代码本地运行正常,但是TOMCAT部署时闪退
  • ¥15 关于#python#的问题
  • ¥15 主机可以ping通路由器但是连不上网怎么办
  • ¥15 数据库一张以时间排好序的表中,找出多次相邻的那些行
  • ¥50 关于DynamoRIO处理多线程程序时候的问题
  • ¥15 kubeadm部署k8s出错
  • ¥15 Abaqus打不开cae文件怎么办?
  • ¥20 双系统开机引导中windows系统消失问题?
  • ¥15 小程序准备上线,软件开发公司需要提供哪些资料给甲方
  • ¥15 关于生产日期批次退货退款,库存回退的问题