已知树的前序遍历和中序遍历，求后序遍历的方法（转）

已知树的前序遍历和中序遍历，求后序遍历的方法（转）

/*    树中已知先序和中序求后序。
      如先序为：abdc,中序为：bdac .
      则程序可以求出后序为：dbca 。此种题型也为数据结构常考题型。
    算法思想：先序遍历树的规则为中左右，则说明第一个元素必为树的根节点，比如上例
中的a就为根节点,由于中序遍历为：左中右，再根据根节点a，我们就可以知道，左子树包含
元素为：db，右子树包含元素：c，再把后序进行分解为db和c（根被消去了），然后递归的
进行左子树的求解（左子树的中序为：db，后序为：db），递归的进行右子树的求解（即右
子树的中序为：c，后序为：c）。如此递归到没有左右子树为止。
关于“已知先序和后序求中序”的思考：该问题不可解，因为对于先序和后序不能唯一的确定
中序，比如先序为 ab，后序为ba，我只能知道根节点为a，而并不能知道b是左子树还是右子树
，由此可见该问题不可解。当然也可以构造符合中序要求的所有序列。

2004.12.5
*/
#include <stdio.h>
int find(char c,char A[],int s,int e) /* 找出中序中根的位置。 */
{
int i;
for(i=s;i<=e;i++)
      if(A[i]==c) return i;
}
/* 其中pre[]表示先序序，pre_s为先序的起始位置，pre_e为先序的终止位置。 */
/* 其中in[]表示中序，in_s为中序的起始位置，in_e为中序的终止位置。 */
/* pronum()求出pre[pre_s～pre_e]、in[in_s～in_e]构成的后序序列。 */
void pronum(char pre[],int pre_s,int pre_e,char in[],int in_s,int in_e)
{
char c;
int k;
if(in_s>in_e)    return ;                 /* 非法子树，完成。 */
if(in_s==in_e){printf("%c",in[in_s]); /* 子树子仅为一个节点时直接输出并完成。 */
                  return ;
                  }
c=pre[pre_s];                           /* c储存根节点。 */
k=find(c,in,in_s,in_e);                 /* 在中序中找出根节点的位置。 */
pronum(pre,pre_s+1,pre_s+k-in_s,in,in_s,k-1); /* 递归求解分割的左子树。 */
pronum(pre,pre_s+k-in_s+1,pre_e,in,k+1,in_e); /* 递归求解分割的右子树。 */
printf("%c",c);                         /* 根节点输出。 */
}
main()
{
char pre[]="abdc";
char in[]="bdac";
printf("The result:");
pronum(pre,0,strlen(in)-1,in,0,strlen(pre)-1);
getch();
} 

//..

已知二叉树的先序和中序求后序－转贴自CSDN 

　二叉树的根结点（根据三种遍历）只可能在左右（子树）之间，或这左子树的左边，或右子树的右边。 
如果已知先序和中序（如果是中序和后序已知也可以，注意：如果是前序和后序的求中序是不可能实现的），先确定这棵二叉树。 
步骤：1，初始化两个数组，存放先序合中序。 
2，对比先序和中序，在中序忠查找先序的第一个元素，则在中序遍历中将这个元素的左右各元素分成两部分。即的左边的部分都在这个元素的左子树中，右边的部分都在右子树中。 
3，然后从从先序的第二个元素开始继续上面的步骤。 

如 先序：1 2 3 4 5 6 7 8 9 10 11
后序：3 2 5 4 1 7 9 8 11 10 6 


level 1: 1 
2: 2 3 
3: 3 4 7 
4: 5 8 
5: 9 10 
6: 11 




这个太简单了，用个递归就可以，我到是有完整的代码，如下： 
// tree.cpp : Defines the entry point for the console application. 
// 

#include "stdafx.h" 
#include "string.h" 

typedef struct node 
{ 
char data; 
struct node *lchild,*rchild; 
}BinNode; 
typedef BinNode *BinTree; 
BinNode *CreateNode(char c) 
{ 
BinNode *n1=new BinNode; 
n1->data=c; 
n1->lchild=NULL; 
n1->rchild=NULL; 
return n1; 
} 
int searchchar(char c,char *order) 
{ 
for(int i=0;i<strlen(order);i++) 
{ 
if(c==order[i]) 
return i; 

} 
return -1; 
} 

BinNode* CreateTree(char *pre,char *in) 
{ 
char c=pre[0]; 
char temppre[100]; 
char tempin[100]; 
char *p; 
int i=0; 
BinNode* bnode; 
if(pre=='\0') 
return NULL; 

memset(temppre,0,100); 
memset(tempin,0,100); 

bnode=CreateNode(c); 
i=searchchar(pre[0],in); 
if(i==-1) 
return 0; 
p=in; 
strncpy(tempin,p,i); 
p=pre; 
strncpy(temppre,p+1,i); 
bnode->lchild=CreateTree(temppre,tempin);//left 

memset(tempin,0,100); 
memset(temppre,0,100); 

p=in+i+1; 
strncpy(tempin,p,strlen(in)-i); 
p=pre+i+1; 
strncpy(temppre,p,strlen(in)-i); 
bnode->rchild=CreateTree(temppre,tempin); //right 
return bnode; 
} 

void POSTORDER(BinNode *t) 
{ 
if(t) /*二叉树t非空*/ 
{ 
POSTORDER(t->lchild); /*后序遍历*t的左子树*/ 
POSTORDER(t->rchild); /*后序遍历*t的右子树*/ 
printf("\t%c",t->data); /*访问结点*/ 
} 
} 

int main(int argc, char* argv[]) 
{ 
char preorder[100]; 
char inorder[100]; 

BinNode* Head; 

do{ 
printf("请输入前序序列\n"); 
scanf("%s",preorder); 
printf("请输入中序序序列\n"); 
scanf("%s",inorder); 
}while(strlen(preorder)!=strlen(inorder)); 

Head=CreateTree(preorder,inorder); 
printf("后序序列为:"); 
POSTORDER(Head); 
printf("\n"); 
// printf("%ld",strlen(readin)); 
return 0; 
}

posted on 2009-07-19 19:48 Ishuan_CPP 阅读(2621) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


导航

<2009年9月>
日一二三四五六
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜