有人知道怎么用中序序列建立二叉树么?我写了一个很明显的代码!可是不行!(10分)

  • 主题发起人 主题发起人 tigerhacker
  • 开始时间 开始时间
T

tigerhacker

Unregistered / Unconfirmed
GUEST, unregistred user!
//1输入先序字符序列,建立二叉链表
Tree * CreateTreeH()
{
Tree *root;
char c;
if ((c=getchar())=='0') root=NULL;
else
{
root=(Tree *)malloc(sizeof(Tree));
root->data=c;
root->lchild=CreateTreeH();
root->rchild=CreateTreeH();
}
return root;
}
//这是先序的,可以成功
//2输入中序字符序列,建立二叉链表
Tree * CreateTreeM()
{
Tree *root;
char c;
if ((c=getchar())=='0') root=NULL;
else
{
root=(Tree *)malloc(sizeof(Tree));
root->lchild=CreateTreeM();
root->data=c;
root->rchild=CreateTreeM();
}
return root;
}
//这是中序的,不行!!
有人知道为什么么?
 
Delphi 的还给你看看,C#还没学会!不好意思
 
问题解决了!现在把我的分析结果写出来!
这个问题么,不知道有多少人想过!也不知道有多少人去尝试着写过!我在网络上找了一下相关的代码.奇怪的是,提出这个问题的人倒是有几个!很少!但是都是没人解答的!可惜可惜!有意思了阿!可不可以实现都是一个迷题!(书上也没有提到能不能建立这个问题!连清华大学的那个严老师的讲座里面也没有提到过这个问题!)
很自然,想必大多数的朋友都和我想的一样的吧!非常自然!一点问题都没有!可是!当我用这个算法来建立二叉树的时候!问题来了!呵呵!建立出来的树是空树!为什么阿?不会吧!电脑出问题了?嘿嘿!郁闷了!后来去问了老师!现在想起来真是个白痴的问题!很明显!
1
2 3
4 5
6
先看看分析用图的那个二叉树的中序序列吧:0201060403050,仔细看看有什么特点!
我发现的特点一:奇数序号的数据为0,偶数序号的数据不为0
我发现的特点二:第一个数据为0(呵呵!这就是问题的所在!)
看看我们的代码if ((c=getchar())=='0') root=NULL;,呵呵!一开始执行,遇到0了,怎么办!我们的语句的意思是结束了!呵呵!算法,出问题了哦!问题找到了!怎么解决呢?我去问老师的时候!老师说!用栈和队列来试试!我当时也没怎么想!说回去再试试!回宿舍!我开始向着办法用栈来实现,反正就是压栈出栈什么的!搞的复杂死了!最后以失败告终!难道我就这么垃圾么!决定将问题进行到底!开始手工分析二叉树中序带结束符号序列的建立流程!这个呀!不分析不知道!一分析吓一跳!啊呀!看看这颗二叉树的中序序列是什么?
5
3
4
6
1
2
是不是:0201060403050,应该没错吧!嘿嘿!是不是和我们刚才那棵树的中序序列一样呢?呵呵!没错!真的是一样的!可是!这两棵树明显不等价!由此可以证明!给出一个中序带结束符号的序列!不可能建立一个确定的二叉树!哎呀!终于弄明白了!程序也不用去写了!不可能的嘛!嘿嘿!所以:得出结论!给出一个中序带结束符号的序列!不管使用任何方法(不要带其他条件),不可能建立一个确定的二叉树.
 
多人接受答案了。
 
后退
顶部