有关于2叉树的问题
已知先序和中序遍历，来求其的2叉数的数的算法。
我想了一下必须要两个序列才行
大家来提一下思路哈
问题点数：20、回复次数：8Top
1 楼zhai19800722（柠檬王子）回复于 2002-05-23 14:44:06 得分 5
是统计其中的接点的个数吗？Top
2 楼bjay（ben）回复于 2002-05-23 14:55:06 得分 0
题目再说清楚点。Top
3 楼yrwithsh（清脆的杯子）回复于 2002-05-23 15:13:52 得分 0
比如说 -
+ /
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
怎么编程实现？谢谢了哈！
Top
4 楼flyaramy（aramy）回复于 2002-05-23 15:17:05 得分 0
到底要求什么？？？不懂！Top
5 楼hannibalhontani（红冰）回复于 2002-05-23 17:29:59 得分 10
template <class Entry>
Binary_node<Entry>* Binary_tree<Entry>::recursive_pre_mid_creat (char* pre,char* mid,
int pre_i,int mid_i,
int length)
{
int i=0;
Binary_node<Entry>* sub_root;
if (length<=0)
return NULL;
while (i<length&&pre[pre_i]!=mid[mid_i+i])
i++;
sub_root=new Binary_node<Entry>;
sub_root->data=pre[pre_i];
sub_root->left=recursive_pre_mid_creat (pre,mid,pre_i+1,mid_i,i);
sub_root->right=recursive_pre_mid_creat (pre,mid,pre_i+i+1,mid_i+i+1,length-i-1);
return sub_root;
}
template <class Entry>
void Binary_tree<Entry>::pre_mid_creat (char* pre,char* mid,
int pre_i,int mid_i,
int length)
{
root=recursive_pre_mid_creat (pre,mid,pre_i,mid_i,length);
}
大概是这样吧，你自己再看看。Top
6 楼jianhenk（星橙）回复于 2002-05-23 19:09:36 得分 3
你的意思是先有一个“先序”
用程序把他的“中序”“后序”计算出来Top
7 楼julyclyde（Java初学（大学不教只好自己学））回复于 2002-05-23 19:47:28 得分 2
最少一个中序和另外一个，一共2个才可以求出树的Top
8 楼yrwithsh（清脆的杯子）回复于 2002-05-23 22:24:24 得分 0
回复人： julyclyde(争取下次的MVP) ( ) 信誉：136 2002-05-23 19:47:00 得分:0
最少一个中序和另外一个，一共2个才可以求出树的
这是一定的了
#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
