我知道有了一个二叉树先序和中序遍历可以唯一确定一颗二叉树但是.....
但是要怎么做才能生成它呢，
比如先序为Pre[n] 中序为Pre[n]
CreatBiTreeFromPreAndIn(,,,,)有谁知道怎么编写呢？
问题点数：0、回复次数：8Top
1 楼dengsf（drklnk@Radical_Dreamer）回复于 2003-11-01 22:17:08 得分 0
先序序列 的第一个点是树的 根。
在 中序序列 找到这个点，将该点前后的部分分为两段，左边是 左子树 的中序序列，右边是右子树的中序序列。
在 先序序列 里也从左到右分出“相同数目”的两个序列，它们分别是 左右子树 的先序序列。
……
递归思想如上。Top
2 楼CD2006（小英雄）回复于 2003-11-02 13:00:42 得分 0
a
/ \
b c
/ \ /
e f g
\
h
PreOrderTraverse: abefcgh
InOrderTraverse: ebfacgh
Algorithm:
在前序遍历中,第一个节点a为树根,则在中序中找到a,将中序序列一分为二,
ebf,cgh ebf显然为左子树,cgh为右子树,
所以在前序序列中可立刻判断bef,cgh分别为左子树的前序遍历和后序遍历.
设左子树为tree1,右子树为tree2,
问题化归为:已知tree1,tree2的前序,中序遍历,生成tree1,tree2.
对tree1,tree2分别递归调用算法.
Top
3 楼CD2006（小英雄）回复于 2003-11-02 13:03:30 得分 0
I'm sorry.
I have made a mistake!
InOrderTraverse :ebfaghc
Top
4 楼CD2006（小英雄）回复于 2003-11-02 13:10:25 得分 0
不好意思中午没睡觉,错话连篇:
重来:
a
/ \
b c
/ \ /
e f g
\
h
PreOrderTraverse: abefcgh
InOrderTraverse: ebfaghc
Algorithm:
在前序遍历中,第一个节点a为树根,则在中序中找到a,将中序序列一分为二,
ebf,cgh , ebf显然为左子树的前序遍历,cgh为右子树的前序遍历,
所以在前序序列中可立刻判断bef,ghc分别为左子树和右子树的前序遍历.
设左子树为tree1,右子树为tree2,
问题化归为:已知tree1,tree2的前序,中序遍历,生成tree1,tree2.
对tree1,tree2分别递归调用算法.
Top
5 楼LeeMaRS（小菜虎，仍需努力）回复于 2003-11-02 13:27:51 得分 0
http://expert.csdn.net/Expert/FAQ/FAQ_Index.asp?id=699
看这里, FAQ里面就有了.Top
6 楼drmao（drmao）回复于 2003-11-02 19:35:09 得分 0
太谢谢大家了，我在努力中。Top
7 楼Riemann（）回复于 2003-11-09 12:35:50 得分 0
http://expert.csdn.net/Expert/topic/2059/2059607.xml?temp=.1657221上有。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 100
typedef struct node
{
char info;
struct node *llink,*rlink;
}TNODE;
char pred[MAX],inod[MAX];
TNODE *restore(char *,char *,int);
void postorder(TNODE *);
main(int argc,char * *argv)
{
TNODE *root;
if(argc<3)
exit(0);
strcpy(pred,argv[1]);
strcpy(inod,argv[2]);
root=restore(pred,inod,strlen(pred));
postorder(roor);
printf("\n\n");
}
TNODE *restore(char *ppos,char *ipos,int n)
{
TNODE *ptr;
char *rpos;
int k;
if(n<=0)
return NULL;
ptr=(TNODE*)malloc(sizeof(TNODE));
ptr->info=*ppos;
for(rpos=inpos;rpos<ipos+n;rpos++)
if(*rpos==*ppos)
break;
k=rpos-ipos;
ptr->llink=restore(ppos+1,ipos,k);
ptr->rlink=restore(ppos+1+k,rpos+1,n-1-k);
return ptr;
}
void postorder(TNODE *ptr)
{
if(ptr==NULL)return;
postorder(ptr->llink);
postorder(ptr->rlink);
printf("%c",ptr->info);
}Top
8 楼CD2006（小英雄）回复于 2003-11-14 20:26:46 得分 0
#include "iostream"
#include "string.h"
using namespace std;
typedef struct BiTree
{
char data;
struct BiTree * lc,* rc;
} BiTree;
const int
StrMax=100;
char * Pre,* In;
void Init(char * Pre,char * In)
{
cout<<"Enter tree's PreOrder: ";
cin>>Pre;
cout<<"Enter tree's InOrder: ";
cin>>In;
}
void create(BiTree * & cur,int left,int right,int & pos)
{
int i;
for(i=left;In[i]!=Pre[pos];i++); //Find out current subtree's root
cur=new BiTree; //Create root
cur->data=Pre[pos];
cur->lc=cur->rc=0;
if(left<=i-1) //Create root's left subtree
{
pos++;
create(cur->lc,left,i-1,pos);
}
if(i+1<=right) //Create root's right subtree
{
pos++;
create(cur->rc,i+1,right,pos);
}
}
void PostOrderPrint(BiTree * cur)
{
if(cur)
{
PostOrderPrint(cur->lc);
PostOrderPrint(cur->rc);
cout<<cur->data<<" ";
}
}
void main(void)
{
BiTree * Tree;
int pos;
void Init(char * Pre,char * In);
void create(BiTree * & cur,int left,int right,int & pos);
void PostOrderPrint(BiTree * cur);
Pre=new char[StrMax];
In=new char[StrMax];
Init(Pre,In);
pos=0;
create(Tree,0,strlen(In)-1,pos);
cout<<"PostOrderTraverse: ";
PostOrderPrint(Tree);
cout<<endl;
}
Top
