微信号:CyuyanAn

介绍:C语言C++;JAVA安卓系统软件编程,C语言编译器,C语言函数手册,C语言编程技巧,C语言视频教学,C语言考试,C语言软件开发设计,

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

2018-03-14 15:52 C语言JAVA软件编程设计

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

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

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

样例输入
BADC             ADEFGHMZ
BDCA    AEFDHZMG

样例输出
ABCD    GDAFEMHZ
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
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 < length; i++)//在中序序列中找等于根节点的位置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<length;m++)
    {
     if(s1[m]<'A'||s1[m]>'Z')
     {
      printf("第%d个字符输入存在非法字符,请输入大写字母\n",m+1);
   count++;//当检测到非法字符,计数器就自增 
  }
 }
 if(count>0)
 return 0;
    printf("请输入后序序列:");
    scanf("%s",&s2);
    printf("\n");
    for(m=0;m<length;m++)
    {
     if(s2[m]<'A'||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;
}





 
C语言JAVA软件编程设计 更多文章 【新手制作】字符串的精华案例 微信:跳一跳辅助 常量、变量和数据类型 深入Unity 1.x依赖注入容器之一:入门 【Win32开发入门】 关于C++的几个要点
猜您喜欢 【Linux】XCache的使用与配置 [干货]varnish原理|杨过同学 任玉刚:让你的职业迷茫从哪来回哪去 每周阅读清单:Git,程序员,代码风格指南