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

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

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

  [題目分析]在中序全線索化T樹的P結點上插入以X為根的中序全線索化二叉樹要對X有無左右子樹進行討論並修改X左(右)子樹上最左結點和最右結點的線索在中序線索樹上查找某結點p的前驅的規律是若p>ltag=則p>lchild就指向前驅否則其前驅是p的左子樹上按中序遍歷的最後一個結點查找某結點p的後繼的規律是若p>rtag=則p>rchild就指向後繼否則其後繼是p的右子樹上按中序遍歷的第一個結點

  int TreeThrInsert(BiThrTree TPX)
  //在中序全線索二叉樹T的結點P上插入以X為根的中序全線索二叉樹返回插入結果信息
  {if(P>ltag== && P>rtag==) {printf(P有左右子女插入失敗\n) return(); }
  if(P>ltag==)    //P有左子女將X插為P的右子女
  {if(X>ltag==) X>lchild=P;  //若X無左子樹 X的左線索(前驅)是P
  else  //尋找X的左子樹上最左(下)邊的結點
  {q=X>lchild;
  while(q>ltag==) q=q>lchild;
  q>lchild=P;
  }
  if(X>rtag==)    //修改X的右線索
  X>rchild=P>rchild;  //將P的右線索改為X的右線索
  else  //找X右子樹最右面的結點
  {q=X>rchild; while(q>rtag==) q=q>rchild;
  q>rchild=P>rchild;
  }
  P>rtag=;P>rchild=X;   //將X作為P的右子樹
  } //結束將X插入為P的右子樹
  else    //P有右子女將X插入為P的左子女
  {if(X>ltag==)    //X無左子女
  X>lchild=P>lchild;  //將P的左線索改為X的左線索
  else    //X有左子女找X左子樹上最左邊的結點
  {q=X>lchild;
  while(q>ltag==) q=q>lchild;
  q>lchild=P>lchild;
  }
  if(X>rtag==) X>rchild=P;   //若X無右子樹則X的右線索是P
  else      //X有右子樹查其右子樹中最右邊的結點將該結點的後繼修改為P
  {q=X>rchild;
  while(q>rtag==) q=q>rchild;
  q>rchild=P;
  }
  P>ltag=; //最後將P的左標記置
  P>lchild=X; //P的左子女鏈接到X
  } //結束將X插入為P的左子女
  }  //結束Tree Thrfnsert

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


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