The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

已知树的前序遍历和中序遍历,求后序遍历的方法(转)

/*    树中已知先序和中序求后序。
      如先序为: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 
11 
22 3 
33 4 7 
45 8 
59 10 
611 




这个太简单了,用个递归就可以,我到是有完整的代码,如下: 
// 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
}
 

本文转自:http://hi.baidu.com/%B0%D9%BE%FD/blog/item/5fb6cca21e6f51afcbefd0fb.html

posted on 2009-03-17 18:20 abilitytao 阅读(7346) 评论(0)  编辑 收藏 引用


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