今天的主題是延續昨天的 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 的方式走訪完畢囉！