拜托!!!!!!!!!!!!!!给出二叉树的中序遍历和前序遍历序列，构造出该二叉树

给出二叉树的中序遍历和前序遍历序列，构造出该二叉树 问题点数：88、回复次数：8Top

1 楼inline（★ 虚函数【虚英语】☆）回复于 2003-12-03 23:45:31 得分 25

//输入中序序列构造的二叉树不唯一  
  //以下给出前序序列构造二叉树的结构及算法:  
   
  #include<iostream.h>  
   
  typedef   char   ElemType;  
  typedef   struct   TNode  
  {  
  ElemType   data;  
  struct   TNode*   lchild;  
  struct   TNode*   rchild;  
  }BTree,   *BTreePtr;  
   
  void   pcreat(BTreePtr&   t)         //前序种植二叉树  
  {  
  char   ch;   t   =   NULL;  
  cin   >>   ch;  
  if(ch   !=   '@')   {                   //输入   ＠   时为空  
  t   =   new   TNode;  
  t->data   =   ch;  
  pcreat(t->lchild);  
  pcreat(t->rchild);  
  }  
  }  
   
  void   porder(const   BTreePtr&   t)         //前序遍历二叉树  
  {  
  if(t)   {  
  cout   <<   t->data;  
  porder(t->lchild);  
  porder(t->rchild);  
  }  
  }  
   
  void   destroytree(BTreePtr&   t)           //砍树  
  {  
  if(t)   {  
  destroytree(t->lchild);  
  destroytree(t->rchild);  
  delete   t;   t   =   NULL;  
  }  
  }  
   
  void   main(void)  
  {  
  BTree*   tree   =   NULL;  
  pcreat(tree);                   //前序种树  
  porder(tree);                   //前序遍历  
  destroytree(tree);         //后序砍树  
  cout   <<   endl;  
  }  
   
  //树结构:                               A  
  //                                           /   \  
  //                                         B       D  
  //                                       /       /   \  
  //                                     C       E       F  
   
  //输入：ABC@@@DE@@F@@  
  //输出：ABCDEFTop

2 楼adingzhang（阿鼎）回复于 2003-12-04 17:40:27 得分 0

谢谢前辈!  
  可能是我没问清楚,问题其实是:输入一棵确定树的前序遍历及其中序遍历序列,构造该二叉树!Top

3 楼adingzhang（阿鼎）回复于 2003-12-04 17:50:10 得分 0

lee0119给出的算法:  
  void   restore(Bitree   &T,int   pre[],int   in[],int   &count,int   low,int   high)  
  {if(count>=MAX)     //MAX是树的结点个数  
  return;  
  else   {  
  if(low==high)  
  T=NULL;  
  else   {  
  T=(bitree)malloc(sizeof(BiNode));  
  T->data=pre[count];  
  for(i=low;i<=high&&in[i]!=pre[count];i++);//在中序序列中找到根结点  
  restore(T->Lchild,pre,in,++count,low,i-1);//构造左子树  
  resore(T->Rchild,ore,in.++count,i+1,high);//构造右子树  
      }  
    }  
  }  
  //  
  //  
  但这样函数参数太多,递归起来算法时间复杂度太大!  
  不知前辈有无更好的算法!Top

4 楼ntxs（别人加薪我加班，数钱数到心发酸T_T）回复于 2003-12-04 17:57:39 得分 10

四大DTop

5 楼ZhangYv（迎着朝阳,走向地狱）回复于 2003-12-04 18:34:56 得分 43

#include<stdio.h>  
  #include<string.h>  
  #include<stdlib.h>  
   
  #define   MAX   100  
   
  typedef   struct   node  
  {  
  char   info;  
  struct   node   *llink,*rlink;  
  }TNODE;  
   
  char   pred[MAX],inod[MAX];  
  TNODE   *restore(char   *,char   *,int);  
  void   postorder(TNODE   *);  
   
  main(int   argc,char   *   *argv)  
  {  
  TNODE   *root;  
  if(argc<3)  
  exit(0);  
  strcpy(pred,argv[1]);  
  strcpy(inod,argv[2]);  
  root=restore(pred,inod,strlen(pred));  
  postorder(roor);  
  printf("\n\n");  
  }  
   
  TNODE   *restore(char   *ppos,char   *ipos,int   n)  
  {  
  TNODE   *ptr;  
  char   *rpos;  
  int   k;  
  if(n<=0)    
  return   NULL;  
  ptr=(TNODE*)malloc(sizeof(TNODE));  
  ptr->info=*ppos;  
  for(rpos=inpos;rpos<ipos+n;rpos++)  
  if(*rpos==*ppos)  
  break;  
  k=rpos-ipos;  
  ptr->llink=restore(ppos+1,ipos,k);  
  ptr->rlink=restore(ppos+1+k,rpos+1,n-1-k);  
  return   ptr;  
  }  
   
  void   postorder(TNODE   *ptr)  
  {  
  if(ptr==NULL)return;  
  postorder(ptr->llink);  
  postorder(ptr->rlink);  
  printf("%c",ptr->info);  
  }    
   
  http://expert.csdn.net/Expert/topic/2059/2059607.xml?temp=.9964563Top

6 楼adingzhang（阿鼎）回复于 2003-12-04 22:37:49 得分 0

谢谢大家!  
  I   must   四大D   from   everyone   of   csdn!  
   
  Top

7 楼ilovedonny（迷失的代码工）回复于 2003-12-04 22:41:55 得分 10

哈哈，楼主也该结贴了吧，楼上那帮兄弟也帮你解释的很清楚了啊~  
  PS：：   ZhangYv(英语－痛苦、绝望)   改名了啊？？你e文很菜啊？？怎么改这么个名字啊？Top

8 楼adingzhang（阿鼎）回复于 2003-12-04 22:58:50 得分 0

to   ilovedonny  
  You   are   welcome!:)  
  I'm   not   ZhangYv,but   a   freshman   on   csdn.  
  希望以后多多指教:)Top

相关问题

• 算法
• csdn
• 遍历
• 序
• 叉树
• tnode
• 构造
• 序列
• btreeptr
• destroytree

• 帖主：adingzhang
• inline
• ntxs
• ZhangYv
• ilovedonny

• C/C++ Blog
• C/C++类图书
• C/C++类源码下载