在二元搜尋樹中搜尋

2019-10-16 22:02:31

搜尋表示在資料結構中查詢或定位某些特定元素或節點。 但是,在二元搜尋樹中搜尋某個特定節點非常容易,因為二元搜尋樹中的元素以特定順序儲存。

  1. 將元素與樹的根進行比較。
  2. 如果專案匹配,則返回節點的位置。
  3. 否則,檢查資料項是否小於根的元素,如果是,則移動到左子樹。
  4. 如果沒有,則移至右子樹。
  5. 遞回地重複此過程,直到找到匹配。
  6. 如果未找到元素,則返回NULL

整個搜尋過程,如下圖所示:

演算法:

search (ROOT, ITEM)
步驟1:
    IF ROOT -> DATA = ITEM OR ROOT = NULL
        返回ROOT
    ELSE
        IF ROOT <ROOT -> DATA
            返回search(ROOT -> LEFT,ITEM)
        ELSE
            返回search(ROOT - > RIGHT,ITEM)
        [IF結束]
  [IF結束]
第2步:結束