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

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

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

  .[題目分析]在中序穿線二叉樹中求某結點p的後序後繼q需要知道p的雙親結點f的信息(中序線索樹的性質若p是f的左子女則f是p的最右子孫的右線索若p是f的右子女則f是p的最左子孫的左線索)找到f後若p是f的右子女則p的後繼是f若p是f的左子女且f無右子女則p的後繼也是f若p是f的左子女且f有右子女則f的右子樹中最左邊的葉子結點是p的後繼因此算法思路是先找p的雙親f根據p是f的左/右子女再確定p的後序後繼

  BiThrTree InThrPostSucc(BiThrTree rp)
  //在中序線索二叉樹r上求結點p(假定存在)的後序後繼結點q)
  {if(p==r)return(null)     //若p為根結點後序後繼為空
  T=p
  while(T>LT==) T=T>LL; //找p的最左子孫的左線索
  q=T>LL;                 //q是 p最左子孫的左線索是p的祖先
  if(q>RL==p) return(q);  //p是q的右子女則q是p後序後繼
  T=p;
  while(T>RT==) T=T>RL; //找p的最右子孫的右線索
  q=T>RL;                 //q是p最右子孫的右線索
  if(q>LL=p)              //若p是q的左子女
  if(q>RT==) return(q);//若p是q的左子女且q無右子女則p的後序後繼是q
  else     //p的雙親q有右子樹則q的右子樹上最左下的葉子結點是p的後繼
  {q=q>RL;
  while(q>LT==||q>RT==)  //找q右子樹中最左下的葉子結點
  {while(q>LT==) q=q>LL; //向左下
  if(q>RT==) q=q>RL;    //若q無左子女但有右子女則向右下直到葉子結點
  }
  return(q); //q是的p後繼
  }
  } //結束InThrPostSucc

  [算法討論] 請注意本題條件標記為時是線索而為時是指向子女

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


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