根据前序中序遍历建立二叉树

根据前序中序遍历建立二叉树(2009-03-20 20:15:28)

【前言】

这个选题源自课上的一个习题，题目提供了二叉树的前序遍历和中序遍历，要求出整个二叉树。刚一做这道题时，还有些迷惑。但是，既然答案是确定的，就一定存在着算法，来求出这个二叉树。经过一些摸索，最终确定了求解算法。

【分析】

二叉树的遍历一共有四种方法，分别是前序遍历、中序遍历、后续遍历和层序遍历。各种方法各有特点，但是中序遍历的特点最好利用。

中序遍历是先遍历左子树，然后依次遍历根节点、右子树。形成的序列，某个节点的左子树节点全部分布于它的左侧，右子树节点全部分布在它的右侧。这样，就可以通过比对子节点和根节点的相对位置，就可以确定这个节点是左孩子还是右孩子了。

而前序遍历是从上向下、从左往右依次进行的，不会在遍历了根和孩子后，又遍历它们中间的节点。这就是说，我们不用考虑插入节点的问题了。

我的想法是，依次扫描前序遍历的序列，第一个是根节点，直接创建。之后的元素要利用中序遍历的结果，与已生成的节点依次比对，来确定该节点是位于左子树还是右子树。重复这个过程，直到找到最终的位置后，续接在这个位置上，成为一个叶子。当然，这个过程是一个递归的过程了。当前序遍历扫描结束时，二叉树就生成完毕了，问题解决。

【算法实现】

程序用两个字符数组来保存前序遍历和中序遍历的结果，将这个字符数组作为参数在模块间传递，以供各模块使用，同时也降低了个模块间的耦合度。设计一个函数来生成二叉树，还有一个函数建立新节点，这个函数要自身递归，还要设计一个函数来扫描字符串，确定应该位于左还是右子树。

值得注意的是，建立新节点的函数要为节点分配内存，所以要采用传址传递，本质是传入指针的指针。另外，还应考虑二叉树的输出问题，这里采用文本模式输出。这里仅仅是一个示例，所以节点数据设计成字符型，以便于理解，而且程序也不对输入的合法性和可行性进行检测。

【源代码】

#include <stdio.h>

#include <conio.h>

#include <alloc.h>

#include <string.h>

#define MAXCOUNT 32

#define LEFT 0

#define RIGHT 1

typedef char Elemtype;

typedef struct BtreeNode

{

Elemtype Data;

struct BtreeNode *LChild,*RChild;

}BTREENODE,*BTREENODEPTR,*BTREE;

typedef struct Pos

{

int x,y;

}BTREENODEPOS;

BTREENODEPOS BtnPos[MAXCOUNT];

void InitBtreeNodePos(void)

{

int i;

for(i=0;i<16;i++)

{

BtnPos[16+i].x=25+i*2;

BtnPos[16+i].y=16;

}

for(i=15;i>=1;i--)

{

BtnPos[i].x=(BtnPos[2*i].x+BtnPos[2*i+1].x)/2;

BtnPos[i].y=BtnPos[2*i].y-2;

}

}

void DestroyBtree(BTREE Root)

{

if(Root==NULL)return;

DestroyBtree(Root->LChild);

DestroyBtree(Root->RChild);

Root->LChild=NULL;

Root->RChild=NULL;

free(Root);

}

void ShowBtree(BTREE Root,int Index)

{

int i,j;

if(Root==NULL)return;

i=Index*2;

j=Index*2+1;

gotoxy(BtnPos[Index].x,BtnPos[Index].y);

printf("%c",Root->Data);

if(i<MAXCOUNT) ShowBtree(Root->LChild,i);

if(j<MAXCOUNT) ShowBtree(Root->RChild,j);

}

int GetLR(char *PreOrder,char *InOrder,int i,int Data)

{

int j=0,k=0;

while(PreOrder[i]!=InOrder[j]) j++;

while(Data!=InOrder[k]) k++;

if(j<k) return LEFT; else return RIGHT;

}

void AddBtreeNode(BTREE *Root,char *PreOrder,char *InOrder,int i)

{

if(*Root==NULL)

{

(*Root)=(BTREENODE*)malloc(sizeof(BTREENODE));

(*Root)->Data=PreOrder[i];

(*Root)->LChild=NULL;

(*Root)->RChild=NULL;

}

else

{

if(GetLR(PreOrder,InOrder,i,(*Root)->Data)==LEFT)

AddBtreeNode(&(*Root)->LChild,PreOrder,InOrder,i);

else

AddBtreeNode(&(*Root)->RChild,PreOrder,InOrder,i);

}

}

BTREE CreatBtreeByOrder(void)

{

char PreOrder[32],InOrder[32];

BTREE Root=NULL;

int i;

printf("Input PreOrder:");

gets(PreOrder);

printf("Input InOrder :");

gets(InOrder);

for(i=0;PreOrder[i]!=0;i++)

AddBtreeNode(&Root,PreOrder,InOrder,i);

return Root;

}

void main()

{

BTREE Root;

clrscr();

InitBtreeNodePos();

Root=CreatBtreeByOrder();

ShowBtree(Root,1);

DestroyBtree(Root);

}

这里是完整版，复制下来就可以直接运行了。下面给出一些测试用例，可以检测这个算法。

第一组：PreOrder:ABDHJEICFG,InOrder:DJHBEIAFCG

第二组：PreOrder:ABDHEICFG,InOrder:DHBIEAFGC

第三组：PreOrder:ABCDEFG,InOrder:BCAFEGD

【总结】

充分利用前序遍历和中序遍历的特点，就可以生成二叉树。如果把前序换成层序，算法不用改动，若换成后序，只需将后续遍历求逆，用这个逆序进行这个算法，也不用作任何改动。可见，这里的中序遍历是很重要的。但是，如果不提供中序遍历，比如说只有前序、后续遍历，是不能确定一个二叉树的，这时算法不好修改，这里就不讨论了。