先序中序遍历建立二叉树问题
本帖最后由 avecparapluie 于 2010-05-08 23:35:32 编辑 /*根据先序和中序遍历的结果建立一棵二叉树，编译调试都通过了，不能正常运行，哪位大神麻烦看一下*/
#include<stdio.h>
#include<stdlib.h>
typedef int ELemType;

typedef struct BiTreeNode{
ELemType data;
struct BiTreeNode* lchild;
struct BiTreeNode* rchild;
}BiTreeNode,*BiTree;

int main(){
void PreInOrd(ELemType preord[],ELemType inord[],int i,int j,int k,int h,BiTree *t);
void CreateTree(ELemType preord[],ELemType inord[],int n,BiTree root);
BiTree R=NULL;
ELemType preorder[]={0,1,2,4,3,5,7,6,8,9}; /*先序遍历结果,0用于占位*/
ELemType inorder[]={0,4,2,1,5,7,3,8,6,9}; /*中序遍历结果，0用于占位*/
CreateTree(preorder,inorder,9,R);
return 0;
}

void CreateTree(ELemType preord[],ELemType inord[],int n,BiTree root){ /*n二叉树结点数目，建立的二叉树放在root中*/
void PreInOrd(ELemType preord[],ELemType inord[],int i,int j,int k,int h,BiTree *t);
void lastOrder(BiTree head);
if(n<=0) root=NULL;
else PreInOrd(preord,inord,1,n,1,n,&root);
lastOrder(root); /*后序遍历输出*/
}

void PreInOrd(ELemType preord[],ELemType inord[],int i,int j,int k,int h,BiTree *t){/*先序序列从i到j,中序序列从k到h，建立的二叉树放在t中*/
int m;
*t=(BiTree)malloc(sizeof(BiTreeNode));
(*t)->data=preord[i]; /*二叉树的根*/
m=k;
while(inord[m]!=preord[i]) /*在中序序列中定位根*/
m++; //m=3,k=1 m=2,k=1
if(m==k)
(*t)->lchild=NULL;
else
PreInOrd(preord,inord,i+1,i+m-k,k,m-1,&((*t)->lchild)); /*左子树的根结点*/
if(m==h)
(*t)->rchild=NULL;
else
PreInOrd(preord,inord,i+m-k+1,j,m+1,h,&((*t)->lchild));
}

void lastOrder(BiTree head) /*后序遍历*/
{
if(head)
{
lastOrder(head->lchild); /*递归遍历左子树*/
lastOrder(head->rchild); /*递归遍历右子树*/
printf("%d\t",head->data);
}
}
[解决办法]
来接个分,呵呵.

/*求助：根据先序和中序遍历的结果建立一棵二叉树，编译调试都通过了，但不能正常运行，大神麻烦帮我看一下*/

#include<stdio.h>
#include<stdlib.h>

typedef int ELemType;

typedef struct BiTreeNode{   
ELemType data;
struct BiTreeNode* lchild;
struct BiTreeNode* rchild;
} BiTreeNode, *BiTree;

void CreateTree(ELemType preord[],ELemType inord[],int n,BiTree *root);
void PreInOrd(ELemType preord[],ELemType inord[],int i,int j,int k,int h,BiTree *t);
void lastOrder(BiTree head);

int main()
{
//void PreInOrd(ELemType preord[],ELemType inord[],int i,int j,int k,int h,BiTree *t); 
 
//void CreateTree(ELemType preord[],ELemType inord[],int n,BiTree root);
  BiTree R=NULL;
ELemType preorder[]={0,1,2,4,3,5,7,6,8,9}; /*先序遍历结果,0用于占位*/
ELemType inorder[]={0,4,2,1,5,7,3,8,6,9}; /*中序遍历结果，0用于占位*/

/*
1,2,4,3,5,7,6,8,9
4,2,1,5,7,3,8,6,9

       1 
   2       3
4       5     6
      7     8   9
后序遍历：
4 2 7 5 8 9 6 3 1
*/

  CreateTree(preorder,inorder,9,&R);   
return 0;        
}

//void CreateTree(ELemType preord[],ELemType inord[],int n,BiTree root)
void CreateTree(ELemType preord[],ELemType inord[],int n,BiTree *root)
{ /*n二叉树结点数目，建立的二叉树放在root中*/
if(n<=0) {
(*root)=NULL;
}
else {
//PreInOrd(preord,inord,1,n,1,n,&root);
PreInOrd(preord,inord,1,n,1,n,root);
}
lastOrder(*root); /*后序遍历输出*/
}

void PreInOrd(ELemType preord[],ELemType inord[],int i,int j,int k,int h,BiTree *t)
{/*先序序列从i到j,中序序列从k到h，建立的二叉树放在t中*/
int m;
*t=(BiTree)malloc(sizeof(BiTreeNode));
//(*t)->data=preord; /*二叉树的根*/
(*t)->data=preord[i];
m=k;   
//while(inord[m]!=preord) { /*在中序序列中定位根*/
while(m <=h&&inord[m]!=preord[i]) { 
m++; //m=3,k=1 m=2,k=1
}
if(m==k) {
(*t)->lchild=NULL;   
}
else { 
PreInOrd(preord,inord,i+1,i+m-k,k,m-1,&((*t)->lchild)); 
}
if(m==h) {
(*t)->rchild=NULL;
}
else {
PreInOrd(preord,inord,i+m-k+1,j,m+1,h,&((*t)->rchild));  //这里是右子树
}
}

void lastOrder(BiTree head) /*后序遍历*/
{
if(head)
{
  lastOrder(head->lchild); /*递归遍历左子树*/
  lastOrder(head->rchild); /*递归遍历右子树*/
  printf("%d\t",head->data);
}
}