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

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

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

  [題目分析]二叉樹結點p所對應子樹的第一個後序遍歷結點q的求法如下若p有左子樹則q是p的左子樹上最左下的葉子結點若p無左子樹僅有右子樹則q是p的右子樹上最左下的葉子結點

  BiTree PostFirst(p)
  {BiTree q=p;
  if (!q) return(null); else
  while(q>lchild || q>rchild); //找最左下的葉子結點
  if(q>lchild) q=q>lchild;   //優先沿左分枝向下去查最左下的葉子結點
  else q=q>rchild;           //沿右分枝去查最左下的葉子結點
  return(q);
  }

  [算法討論]題目求p所對應子樹的第一個後序遍歷結點蘊涵p是子樹的根若p是葉子結點求其後繼要通過雙親

  ()由先序序列A[n]和中序序列B[n]可以確定一棵二叉樹詳見本章四第

  ()void PreInCreat( ElemTypeA[]B[]int lhlh)

  //由二叉樹前序序列A[n]和中序序列B[n]建立二叉樹lh和lh分別為先序序列和
  //中序序列第一和最後結點的下標初始調用時l=l=h=h=n
  {typedef struct {int lhlh; BiTree t; }node;
  BiTree bt;
  int top=i; node s[]p;   //s為棧容量足夠大
  bt=(BiTree)malloc(sizeof(BiNode)); //申請結點空間
  pl=l; ph=h; pl=l; ph=h; pt=bt; s[++top]=p; //初始化
  while(top>)
  {p=s[top]; bt=pt; l=pl; h=ph; l=pl ;h=ph;//取出棧頂數據
  for(i=l;i<=h;i++) if(B[i]==A[l]) break;    //到中序序列中查根結點的值
  bt>data=A[l];                   //A[l]為根結點的值
  if(i==l) bt>lchild=null;        //bt無左子樹
  else   //將建立左子樹的數據入棧
  {bt>lchild=(BiTree)malloc(sizeof(BiNode)); pt=bt>lchild;
  pl=l+; ph=l+il; pl=l; ph=i; s[++top]=p;  }
  if(i==h) bt>rchild=null; //bt無右子樹
  else {bt>rchild=(BiTree)malloc(sizeof(BiNode)); pt=bt>rchild;
  pl=l+il+; ph=h; pl=i+; ph=h; s[++top]=p; }//右子樹數據入棧
  }//while
  }結束PreInCreat

  ()當二叉樹為單支樹時棧深n當二叉樹左右子樹高相等時棧深logn時間復雜度O(n)

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


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