返回顶部

收藏

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

更多

编一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));
}

标签:c++,二叉树

收藏

0人收藏

支持

0

反对

0

发表评论