iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 24
0

今天的主題是延續昨天的 Binary Search Tree,我們要來看其中一種 Traversal 的方法,所謂 Traversal 就是用某種順序來走訪 Binary Search Tree 中的每一個節點。然而今天要來看的是其中一種叫做 Level Order Tree Traversal,又稱為 Breadth-First Search (廣度優先) (另外還有 Depth-First Search,概念上是從根節點開始從左到右依序走訪每一個子樹),以下圖為例,我們從根節點出發,也就是 8,依序從每個 Level (也就是 Level Order) 從左到右地走訪,照此邏輯我們會得到 8 3 10 1 6 14 4 7 13,如果還不是很清楚的話可以參考這個影片囉。
在演算法上我們從根節點開始,用一個變數例如 current 來記錄目前要印出的值,例如一開始是 8,接著會把其左右子節點 (3, 10) Enqueue 進一個 Queue。再來的步驟就是把 Queue 用 Dequeue 取出一個節點,並印出值來,這裡是 3,再把 3 的左右子節點 (1, 6) 給 Enqueue 進 Queue。再回來 Dequeue 得到 10 印出,並把其左右子節點 (這裡只有 14) Enqueue。不斷重複直到 Queue 裡面沒有東西為止就完成了!那就讓我們來走訪昨天所建立出來的各個語言的 Binary Search Tree 吧!


From Wiki


Python 3

class Node:
    def __init__(self, data):
        self.right = None
        self.left = None
        self.data = data

def insert(root, data):
    if root is None:
        return Node(data)
    else:
        if data <= root.data:
          cur = insert(root.left, data)
          root.left = cur
        else:
          cur = insert(root.right, data)
          root.right = cur
        return root

def get_height(root):
    return -1 if root is None else 1 + max(get_height(root.left), get_height(root.right))
    

def level_order(root):
    queue = [root]
    while len(queue) != 0:
        curr = queue[0]
        queue = queue[1:]
        print(str(curr.data) + " ", end = "")
        if curr.left is not None:
            queue.append(curr.left)
        if curr.right is not None:
            queue.append(curr.right)


root = None
root = insert(root, 8)
root = insert(root, 3)
root = insert(root, 10)
root = insert(root, 1)
root = insert(root, 6)
root = insert(root, 14)
root = insert(root, 4)
root = insert(root, 7)
root = insert(root, 13)
level_order(root)
  • 這裡跟之前不同的是多了一個函式 level_order,也就是把開頭所述的演算法給實作出來。首先先把 root 加到 queue 這個 List (記得我們之前用 List 來實作出 Queue)。再來就是我們說的 while loop:把 Queue 中的元素取出來,在印出後再把其左右子節點加到 Queue 中。一直重複這樣的動作直到 Queue 的長度變成 0,也就把這個 BST 用 Level Order Tree Traversal 的方式走訪完畢囉!

上一篇
[Day 22] 種下一棵有用的樹
下一篇
[Day 24] 一條獨一無二的鏈
系列文
30 天把自己榨好榨滿的四週四語言大挑戰!30

尚未有邦友留言

立即登入留言