The Fourth Dimension Space

枯葉北風(fēng)寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢(mèng)令

導(dǎo)航

<

2010年3月

>

日

一

二

三

四

五

六

28

1

2

3

4

5

6

7

8

9

10

11

12

16

18

25

26

27

1

2

3

4

5

6

7

8

9

10

統(tǒng)計(jì)

隨筆 - 414
文章 - 13
評(píng)論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

友情鏈接

n皇后問題精彩分析
RMQ問題的精彩文章
開關(guān)燈問題

搜索

閱讀排行榜

評(píng)論排行榜

已知樹的前序遍歷和中序遍歷，求后序遍歷的方法（轉(zhuǎn)）

/* 樹中已知先序和中序求后序。

如先序?yàn)椋篴bdc,中序?yàn)椋篵dac .

則程序可以求出后序?yàn)椋篸bca 。此種題型也為數(shù)據(jù)結(jié)構(gòu)常考題型。

算法思想：先序遍歷樹的規(guī)則為中左右，則說明第一個(gè)元素必為樹的根節(jié)點(diǎn)，比如上例

中的a就為根節(jié)點(diǎn),由于中序遍歷為：左中右，再根據(jù)根節(jié)點(diǎn)a，我們就可以知道，左子樹包含

元素為：db，右子樹包含元素：c，再把后序進(jìn)行分解為db和c（根被消去了），然后遞歸的

進(jìn)行左子樹的求解（左子樹的中序?yàn)椋篸b，后序?yàn)椋篸b），遞歸的進(jìn)行右子樹的求解（即右

子樹的中序?yàn)椋篶，后序?yàn)椋篶）。如此遞歸到?jīng)]有左右子樹為止。

關(guān)于“已知先序和后序求中序”的思考：該問題不可解，因?yàn)閷?duì)于先序和后序不能唯一的確定

中序，比如先序?yàn)?nbsp;ab，后序?yàn)閎a，我只能知道根節(jié)點(diǎn)為a，而并不能知道b是左子樹還是右子樹

，由此可見該問題不可解。當(dāng)然也可以構(gòu)造符合中序要求的所有序列。

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]構(gòu)成的后序序列。 */

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]); /* 子樹子僅為一個(gè)節(jié)點(diǎn)時(shí)直接輸出并完成。 */

return ;

}

c=pre[pre_s]; /* c儲(chǔ)存根節(jié)點(diǎn)。 */

k=find(c,in,in_s,in_e); /* 在中序中找出根節(jié)點(diǎn)的位置。 */

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); /* 根節(jié)點(diǎn)輸出。 */

}

main()

{

char pre[]="abdc";

char in[]="bdac";

printf("The result:");

pronum(pre,0,strlen(in)-1,in,0,strlen(pre)-1);

getch();

}

//

..

已知二叉樹的先序和中序求后序－轉(zhuǎn)貼自CSDN

　二叉樹的根結(jié)點(diǎn)（根據(jù)三種遍歷）只可能在左右（子樹）之間，或這左子樹的左邊，或右子樹的右邊。

如果已知先序和中序（如果是中序和后序已知也可以，注意：如果是前序和后序的求中序是不可能實(shí)現(xiàn)的），先確定這棵二叉樹。

步驟：1，初始化兩個(gè)數(shù)組，存放先序合中序。

2，對(duì)比先序和中序，在中序忠查找先序的第一個(gè)元素，則在中序遍歷中將這個(gè)元素的左右各元素分成兩部分。即的左邊的部分都在這個(gè)元素的左子樹中，右邊的部分都在右子樹中。

3，然后從從先序的第二個(gè)元素開始繼續(xù)上面的步驟。

如先序：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

這個(gè)太簡(jiǎn)單了，用個(gè)遞歸就可以，我到是有完整的代碼，如下：

// 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); /*訪問結(jié)點(diǎn)*/

}

int main(int argc, char* argv[])

{

char preorder[100];

char inorder[100];

BinNode* Head;

do{

printf("請(qǐng)輸入前序序列\(zhòng)n");

scanf("%s",preorder);

printf("請(qǐng)輸入中序序序列\(zhòng)n");

scanf("%s",inorder);

}while(strlen(preorder)!=strlen(inorder));

Head=CreateTree(preorder,inorder);

printf("后序序列為:");

POSTORDER(Head);

printf("\n");

// printf("%ld",strlen(readin));