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

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

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

  [題目分析]在中序線索樹中非遞歸查找數據域為A的結點(設該結點存在其指針為P)並將數據域為x的Q結點插入到左子樹中若P無左子女則Q成為P的左子女原P的左線索成為Q的左線索Q的右線索為P若P有左子樹設P左子樹中最右結點的右線索是結點Q結點Q的右線索是P

  void InThrInsert(BiThrTree TQ; ElemType A)
  //在中序線索二叉樹T中查找其數據域為A的結點並在該結點的左子樹上插入結點Q
  {BiThrTree P=T;
  while(P)
  {while(P>LT== && P>data!=A) P=P>LL; //沿左子樹向下
  if (P>data==A) break;    //找到數據域為A的結點退出循環
  while(P>RT==) P=P>RL;  //還沒找到數據域為A的結點沿右線索找後繼
  P=P>RL;   //沿右子樹向下
  }
  if(P>LT==)  //P沒有左子樹Q結點插入作P的左子女
  {Q>LL=P>LL; Q>LT= //將P的左線索作為Q的左線索
  }
  else  //P有左子樹應修改P的左子樹最右結點的線索
  {Q>LL=P>LL;Q>LT=; //Q成為P的左子女
  s=Q>LL;             //s指向原P的左子女
  while(s>RT==) s=s>RL; //查找P的左子樹最右邊的結點
  s>RL=Q;                 //原P左子樹上最右結點的右線索是新插入結點Q
  }
  P>LT=;P>LL=Q; //修改P的標記和指針
  Q>RT=;Q>RL=P; //將Q鏈為P的左子女其中序後繼是P;
  }//結束InThrInsert

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


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