The Fourth Dimension Space

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

統計

隨筆 - 414
文章 - 13
評論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

友情鏈接

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

搜索

閱讀排行榜

評論排行榜

已知樹的前序遍歷和中序遍歷，求后序遍歷的方法（轉）

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

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