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

如何學習數據結構[3]

2013-11-12 23:41:59  來源: 數據結構 

  對於總結共性問題上這裡舉一小個例子(呵呵我當初總結出這個並且和kaoyancom斑竹一具討論確定後三天就在年交大第一題考出類似東東)比如樹的遍歷不管是遞歸還是非遞歸也不管是線索樹還是頭結點有父母信息的樹它的遍歷其實就是一個尋找到遍歷的第一個結點然後再尋找它的後繼結點的過程我們歸納到此處就可以試著總結一下三種遍歷的後繼結點是哪個有幾種情況
對於前序遍歷它的後繼如下

  ()若有左孩子則後繼是左孩子
  ()若無左孩子有右孩子則後繼是右孩子
  ()若既無左孩子又無右孩子則是一片葉子再討論
  (a)若是其父母的左孩子且父母有右孩子則後繼是父母的右孩子
  (b)若是其父母的左孩子且父母無右孩子
  (c)若是其父母的右孩子

  bc都表示這是某個節點的左子樹前序遍歷的最後一個節點則需要找第一個有右子樹的左祖先(定義左祖先即找第一個使得當前節點在這個祖先的左子樹上)然後後繼就是這個祖先的右孩子

[]  []  []  []  


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