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

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

2013-11-15 14:58:45  來源: 數據結構 

   後序線索樹中結點的後繼要麼是其右線索(當結點的rtag=時)要麼是其雙親結點右子樹中最左下的葉子結點所以只有當二叉樹只有根或樹中任一結點均無右子樹時進行遍歷才不用棧其遍歷程序段如下

  while(p>ltag==)p==p>lchild; //找最左下葉子結點
  while(p>rchild!=null){visit(p>data); //訪問結點
  p=p>rchild;} //沿線索向上

  對前序線索二叉樹當二叉樹非空時若其結點有左子女(ltag=左子女是後繼否則若結點有右子女(rtag=則右子女是後繼若無右子女(rtag=右子女是線索也指向後繼所以對任何前序線索二叉樹進行前序遍歷均不需使用棧

  .左右子樹均不空的二叉樹先序線索化後空指針域為個(最後訪問結點的右鏈為空)

  .if(p>ltag==) return(p>lchild);//左子女不空左子女為直接後繼結點
  else return(p>rchild);          //左子女空右子女(或右線索)為後繼

   後序線索樹中結點的後繼(根結點無後繼)要麼是其右線索(當結點的rtag=時)要麼是其雙親結點右子樹中最左下的葉子結點對中序線索二叉樹某結點若其左標記等於則左子女為線索指向直接前驅否則其前驅是其左子樹上按中序遍歷的最後一個結點

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


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