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

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

2013-11-15 15:37:09  來源: 數據結構 


  .BiThrTree InSucc(BiThrTree Tp)  //在對稱序穿線樹T中查找給定結點p的中序後繼
  {if(p>rtag==)q=p>rchild;   //若p的右標志為用其右指針指向後繼
  else {q=p>rchild; while(q>ltag==) q=q>lchild; }//p的後繼為其右子樹中最左下的結點
  return (q);
  }//結束InSucc

  .[題目分析]在後序序列中若結點p有右子女則右子女是其前驅若無右子女而有左子女則左子女是其前驅若結點p左右子女均無設其中序左線索指向某祖先結點f(p是f右子樹中按中序遍歷的第一個結點)若f有左子女則其左子女是結點p在後序下的前驅若f無左子女則順其前驅找雙親的雙親一直繼續到雙親有左子女(這時左子女是p的前驅)還有一種情況若p是中序遍歷的第一個結點結點p在中序和後序下均無前驅

  BiThrTree InPostPre (BiThrTree tp)
  //在中序線索二叉樹t中求指定結點p在後序下的前驅結點q
  {BiThrTree q;
  if (p>rtag==) q=p>rchild;       //若p有右子女則右子女是其後序前驅
  else if (p>ltag==) q=p>lchild;  //若p無右子女而有左子女左子女是其後序前驅
  else  if(p>lchild==null) q=null;//p是中序序列第一結點無後序前驅
  else //順左線索向上找p的祖先若存在再找祖先的左子女
  {while(p>ltag== && p>lchild!=null) p=p>lchild;
  if(p>ltag==) q=p>lchild;  //p結點的祖先的左子女是其後序前驅
  else  q=null;    //僅右單枝樹(p是葉子)已上到根結點p結點無後序前驅
  }
  return(q); }//結束InPostPre

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


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