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

发布时间：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发布于计算机 网络,转载请注明出处：二叉树前序和中序序列构造该二叉树

关键词：