一本久久综合,国内久久精品,亚洲久久成人

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

/* 樹(shù)中已知先序和中序求后序。

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

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

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

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

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

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

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

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

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

，由此可見(jiàn)該問(wèn)題不可解。當(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 ; /* 非法子樹(shù)，完成。 */

if(in_s==in_e){printf("%c",in[in_s]); /* 子樹(shù)子僅為一個(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); /* 遞歸求解分割的左子樹(shù)。 */

pronum(pre,pre_s+k-in_s+1,pre_e,in,k+1,in_e); /* 遞歸求解分割的右子樹(shù)。 */

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();

}

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

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

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

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

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

3，然后從從先序的第二個(gè)元素開(kāi)始繼續(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) /*二叉樹(shù)t非空*/

{

POSTORDER(t->lchild); /*后序遍歷*t的左子樹(shù)*/

POSTORDER(t->rchild); /*后序遍歷*t的右子樹(shù)*/

printf("\t%c",t->data); /*訪問(wèn)結(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));

return 0;

}

本文轉(zhuǎn)自：http://hi.baidu.com/%B0%D9%BE%FD/blog/item/5fb6cca21e6f51afcbefd0fb.html

posted on 2009-03-17 18:20 abilitytao 閱讀(7387) 評(píng)論(0) 編輯收藏引用

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

The Fourth Dimension Space

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

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