根据中序后序构造二叉树,若构造失败,怎么设置报错

/*

给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,长度

输入格式:两行,每行一个字符串,分别表示中序和后序排列

输出格式:一个字符串,表示所求先序排列

样例输入

BADC ADEFGHMZ

BDCA AEFDHZMG

样例输出

ABCD GDAFEMHZ

*/

#include

#include

#include

struct node//定义存储结构

{

char data;

struct node *lchild, *rchild;

};

char s1[50], s2[50];//s1指的是中序,s2指后序排列

struct node *creat(int length, char *s1, char *s2)//根据二叉树的后序序列和中序序列创建二叉树

{//s2存放后序序列,s1存放中序序列,length为二叉树结点个数

int i;

if(length == 0)//判断输入的字符是否为空

return NULL;

struct node *root;//定义一个指向node类型的指针root

root = (struct node*)malloc(sizeof(struct node));//在内存中为root分配一个动态的存储空间

root -> data = s2[length-1];//根结点的值

for(i = 0; i

{

if(s1[i] == root -> data)//如果中序排列中的元素与后序排列中最后一个元素相同,跳出循环;

break;//这个相同元素则为根节点

}

root -> lchild = creat(i, s1, s2);//递归构造左子树 左子树节点个数,左中序,左后序

root -> rchild = creat(length - i - 1, s1 + i + 1, s2 + i);//递归构造右子树 右子树节点个数,右中序,右后序

return root;

}

void xianxv(struct node *root)

{

if(root)

{

printf("%c", root -> data);

xianxv(root -> lchild);

xianxv(root -> rchild);

}

}//先序遍历

int main()

{

int length,m;

int count=0;//定义一个计数器

system("color 3F");//设置界面背景颜色

printf(" 求先序序列 1604031045 朱涛 \n\n");

printf("请输入中序序列:");

scanf("%s",&s1);

printf("\n");

length = strlen(s1);//读取输入的字符串的长度

if(length>8)//控制输入的字符长度

{

printf("输出字符超出字数限制,错误!!");

return 0; //终止程序

}

for(m=0;m

{

if(s1[m]'Z')

{

printf("第%d个字符输入存在非法字符,请输入大写字母\n",m+1);

count++;//当检测到非法字符,计数器就自增

}

}

if(count>0)

return 0;

printf("请输入后序序列:");

scanf("%s",&s2);

printf("\n");

for(m=0;m

{

if(s2[m]'Z')

{

printf("第%d个字符输入存在非法字符,请输入大写字母\n",m+1);

count++;

}

}

if(count>0)

{

return 0;

}

printf("先序序列为:");

struct node *root;//定义一个root指针

root = creat(length, s1, s2);//递归构造二叉树

xianxv(root);

printf("\n");

return 0;

}

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20180314A0XSL600?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券