发布时间: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发布于计算机 网络,转载请注明出处:二叉树前序和中序序列构造该二叉树
关键词:
下一篇:隔壁次数,数字排序难题