编程论坛
注册
登录
编程论坛
→
C++教室
求二叉树的前序遍列!
雪色朝阳
发布于 2010-03-18 17:46, 896 次点击
已知某二叉树的后序遍历序列是DACBE,中序遍历序列是DEBAC,如何求他的前序遍列?请详细说明!谢谢!
[
本帖最后由 雪色朝阳 于 2010-3-19 10:08 编辑
]
8 回复
#2
qlc00
2010-03-18 18:20
你的这道题就有问题,没有那样的二叉树!
#3
smltq
2010-03-19 08:49
ab绝对有问题
#4
玩出来的代码
2010-03-19 13:57
在后序中找中序序列中的字符在后序中最右边的字符,,
中序DEBAC,后序DACBE,
第一个字符E, 先序 E
此时中序分为D,BAC两部分,再看左子树一个D, ED
右子树BAC找到B, EDB
。。。得先序为EDBCA
#5
雪色朝阳
2010-03-19 14:28
回复 4楼 玩出来的代码
还是不懂,可以说一下做这类题的方法吗?
#6
玩出来的代码
2010-03-19 15:03
程序代码:
BiTree CreatBT(
char
*in,
char
*post,
int
n,
int
m)
{
//
in中序序列,post后序n中序的个数m长度
char
*p,*q,*maxp;
int
maxin,w,r;
BiTree T;
r=-
1
;
if
(n<=
0
)
return
NULL;
//
思想:在后序中找中序序列中的字符在后序中最右边的字符
for
(p=in;p<in+n;p++)
for
(q=post;q<post+m;q++)
{
if
(*p==*q)
{
w=q-post;
if
(w>r)
{
r=w;
//
保存后序中的字符的位置
maxp=p;
/*
保存找到的字符为递归右子树准备
*/
maxin=p-in;
/*
递归左子树准备
*/
}
}
}
T=(BiTree)malloc(
sizeof
(BNode));
T->data=post[r];
T->lchild=CreatBT(in,post,maxin,m);
T->rchild=CreatBT(maxp+
1
,post,n-maxin-
1
,m);
return
T;
}
找了一段程序,你看看,这种题……,也就只是根据中序后序构造先序,或是根据先序中序构造后序……
#7
smltq
2010-03-19 15:14
已知某二叉树的后序遍历序列是DACBE,中序遍历序列是DEBAC,如何求他的前序遍列?请详细说明!谢谢!
已知二叉树的后序和中序,可以确定一课树,这课树为:
E
D B
C
A
所以,它的前序为:EDBCA
[
本帖最后由 smltq 于 2010-3-19 15:17 编辑
]
#8
chsteven
2010-03-19 15:38
以下是引用
smltq
在2010-3-19 15:14:13的发言:
已知某二叉树的后序遍历序列是DACBE,中序遍历序列是DEBAC,如何求他的前序遍列?请详细说明!谢谢!已知二叉树的后序和中序,可以确定一课树,这课树为:
E
D B
C
A
...
你上面这个树的中序是DEBAC吗?
#9
smltq
2010-03-19 16:55
E
D B
C
A
sorry,前面偶把树画错了……
1