熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第六章 答案 (五)[20]

2013-11-15 15:38:15  來源: 數據結構 

  [題目分析]對一般二叉樹僅根據一個先序中序後序遍歷不能確定另一個遍歷序列但對於滿二叉樹任一結點的左右子樹均含有數量相等的結點根據此性質可將任一遍歷序列轉為另一遍歷序列(即任一遍歷序列均可確定一棵二叉樹)

  void PreToPost(ElemType pre[] post[]int lhlh)
  //將滿二叉樹的先序序列轉為後序序列lhlh是序列初始和最後結點的下標
  {if(h>=l)
  {post[h]=pre[l];    //根結點
  half=(hl)/;      //左或右子樹的結點數
  PreToPost(prepostl+l+halfll+half)  //將左子樹先序序列轉為後序序列
  PreToPost(prepostl+half+hl+halfh)  //將右子樹先序序列轉為後序序列
  }  }//PreToPost

  BiTree IntoPost(ElemType in[]post[]int lhlh)
  //in和post是二叉樹的中序序列和後序序列lhlh分別是兩序列第一和最後結點的下標
  {BiTree bt=(BiTree)malloc(sizeof(BiNode));//申請結點
  bt>data=post[h];//後序遍歷序列最後一個元素是根結點數據
  for(i=l;i<=h;i++) if(in[i]==post[h])break;//在中序序列中查找根結點
  if(i==l) bt>lchild=null;  //處理左子樹
  else bt>lchild=IntoPost(inpostlill+il)
  if(i==h) bt>rchild=null;  //處理右子樹
  else bt>rchild=IntoPost(inposti+hl+ilh);
  return(bt);  }

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/23720.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.