您的位置:澳门402永利com > 计算机 网络 > 二叉树前序和中序序列构造该二叉树

二叉树前序和中序序列构造该二叉树

发布时间:2019-09-24 14:09编辑:计算机 网络浏览(146)

    编一C程序,它能依靠输入的二叉树前序和中序连串来组织该二叉树,并能输出该二叉树的后序体系和该二

    叉树叶的结点的个数以及该二叉树高度。(输入次序是:表示前序连串的字符串、表示中序系列的字符串)

    #include<stdio.h>
    #include<malloc.h>
    #include<string.h>
    void exit(int);
    #define MAX 100
    typedef struct node{
        char d;
        struct node *lchild,*rchild;
    }Tnode;
    
    void MK(char in[],char is,char ie,char pre[],char pres,char pree,Tnode **r)
    {
        int i;
        if(is>ie||pres>pree)
            *r=NULL;
        else{
            *r=malloc(sizeof(Tnode));
            (*r)->d=pre[pres];
            for(i=is;i<=ie;i++){
                if(in[i]==pre[pres]){
                MK(in,is,i-1,pre,pres+1,pres+i-is,&(*r)->lchild);
                MK(in,i+1,ie,pre,pres+i-is+1,pree,&(*r)->rchild);
                break;
                }
                if(i>ie){
                    printf("输入错误!\n");
                    exit(1);
                }
            }
        }
    }
    void postorder(Tnode *r)
    {
        if(r){
            postorder(r->lchild);
            postorder(r->rchild);
            printf("%c",r->d);
        }
    }
    int leaf(Tnode *r)
    {
        if(r==NULL)
            return 0;
        else
            if(r->lchild==NULL&&r->rchild==NULL)
                return 1;
            else
                return leaf(r->lchild)+leaf(r->rchild);
    }
    int height(Tnode *r)
    {
        int h1,h2;
        if(r==NULL)
            return 0;
        else{
            h1=height(r->lchild);
            h2=height(r->rchild);
            return 1+(h1>h2?h1:h2);
        }
    }
    void main()
    {
        Tnode *r=NULL;
        char in[MAX],pre[MAX];
        printf("请输入前序序列:\n");
        gets(pre);
        printf("请输入中序序列:\n");
        gets(in);
        MK(in,0,strlen(in)-1,pre,0,strlen(pre)-1,&r);
        printf("\n后序遍历序列为:\n");
        postorder(r);
        printf("\n叶结点的个数为:%d\n",leaf(r));
        printf("\n高度为:%d\n",height(r));
    }
    //该片段来自于http://outofmemory.cn
    

    本文由澳门402永利com发布于计算机 网络,转载请注明出处:二叉树前序和中序序列构造该二叉树

    关键词: