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

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

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

  [題目分析] 刪除以元素值x為根的子樹只要能刪除其左右子樹就可以釋放值為x的根結點因此宜采用後序遍歷刪除值為x結點意味著應將其父結點的左(右)子女指針置空用層次遍歷易於找到某結點的父結點本題要求刪除樹中每一個元素值為 x的結點的子樹因此要遍歷完整棵二叉樹

  void  DeleteXTree(BiTree  bt)  //刪除以bt為根的子樹
  {DeleteXTree(bt>lchild); DeleteXTree(bt>rchild);//刪除bt的左子樹右子樹
  free(bt);  }// DeleteXTree                       //釋放被刪結點所占的存儲空間
  void  Search(B:Tree btElemType x)
  //在二叉樹上查找所有以x為元素值的結點並刪除以其為根的子樹
  {BiTree Q[];//Q是存放二叉樹結點指針的隊列容量足夠大
  if(bt)
  {if(bt>data==x) {DeleteXTree(bt); exit();}//若根結點的值為x則刪除整棵樹
  {QueueInit(Q); QueueIn(Qbt);
  while(!QueueEmpty(Q))
  {p=QueueOut(Q);
  if(p>lchild)               // 若左子女非空
  if(p>lchild>data==x)    //左子女結點值為 x應刪除當前結點的左子樹
  {DeleteXTree(p>lchild); p>lchild=null;} //父結點的左子女置空
  else Enqueue (Qp>lchild);// 左子女入隊列
  if(p>rchild)                // 若右子女非空
  if(p>rchild>data==x)     //右子女結點值為 x應刪除當前結點的右子樹
  {DeleteXTree(p>rchild);   p>rchild=null;} //父結點的右子女置空
  else Enqueue (Qp>rchild);// 右子女入隊列
  }//while
  }//if(bt)  }//search

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


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