有关于2叉树的问题
已知先序和中序遍历，来求其的2叉数的数的算法。
我想了一下必须要两个序列才行
比如说 -
+ /
a * e f
b -
c d (a+b*(c-d))-e/f
它的先序遍历为：-+a*b-cd/ef
它的中序遍历为：a+b*c-d-e/f
那么给了你一个2叉树的先序遍历及中序遍历
要求你编程求出这个2叉树，也就是要先确定存在后
在求出表达式: (a+b*(c-d))-e/f
怎么编程实现？谢谢了哈！
问题点数：20、回复次数：6Top
1 楼sylmoon（专注Oracle）回复于 2002-05-24 18:56:40 得分 0
研究研究Top
2 楼fangrk（加把油，伙计！）回复于 2002-05-24 19:03:13 得分 5
《程序系统设计师》（人民邮电，新大纲）P254Top
3 楼fangrk（加把油，伙计！）回复于 2002-05-24 19:04:00 得分 5
P524Top
4 楼LeeMaRS（小菜虎，仍需努力）回复于 2002-05-24 19:14:26 得分 5
能保证前序和中序中都没有重复的元素吗?
如果能 则保证有唯一的一棵二叉树.Top
5 楼vanhui（飘零辉）回复于 2002-05-25 00:43:54 得分 5
一本英文的数据结构教材上有提到，通过已知条件则保证有唯一的一棵二叉树.
但算法不详Top
6 楼yrwithsh（清脆的杯子）回复于 2002-05-26 19:53:08 得分 0
我给一个程序，大家讨论一下
#include<iostream.h>
class treenode
{
int data;
treenode* lchild;
treenode* rchild;
treenode* father;
public:
treenode()
{
lchild=0;
rchild=0;
father=0;
}
friend int search(int a);
friend treenode* creattree(int nod1[],int nod2[],int n);
friend void tre(treenode* m);
~treenode()
{}
};
treenode* p;
int search(int a)
{
treenode *search;
search=p;
int sign=0;
while(search!=0)
{
if(a==search->data)
{
sign=1;
p=search;
return sign;
}
search=search->father;
}
return sign;
}
treenode* creattree(int nod1[],int nod2[],int n) //ÒÑÖª±éÀú½ÚµãÐòÁй¹Ôì¶þ²æÊ÷
{
treenode* head;
head=new treenode;
head->data=nod1[0];
head->father=0;
p=head;
int i=1,j=0;
int biaoji=0;
while (i<n)
{
if(search(nod2[j]))
{
biaoji=1;
j++;
}
if(!search(nod2[j]))
{
if(biaoji==1)
{
treenode* tn;
tn=new treenode;
tn->data=nod1[i];
p->rchild=tn;
tn->father=p;
p=p->rchild;
i++;
}
if(biaoji==0)
{
treenode* tn;
tn=new treenode;
tn->data=nod1[i];
p->lchild=tn;
tn->father=p;
p=p->lchild;
i++;
}
biaoji=0;
}
}
return head;
}
void tre(treenode* m)
{
if(m!=0)
{
tre(m->lchild);
cout<<char(m->data);
tre(m->rchild);
}
}
void main()
{
int k;
int l1[8]={'b','a','d','c','e'};
int l2[8]={'a','b','c','d','e'};
treenode* nod;
nod=creattree(l1,l2,5);
tre(nod);
cin>>k;
}
Top
