iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 23
0

今天我們要來看的是 Binary Search Tree (BSTs)。Tree 是由有限節點組成具有層次關係的集合。以下圖為例,最上面的節點稱作根節點 (Root),也就是沒有父節點 (Parent)。而每個節點會有零個以上的子節點 (Children)。每個節點都只能有一個父節點 (除了根節點)。在一棵樹裡面是沒有 Cycle 的,也就是你不會在一棵樹裡頭看到環。由於這不是專門介紹資料結構的文章,所以更多細節請參考這裡
From Wiki
From Wiki

那麼 Binary Search Tree,也就是二元搜尋樹又是什麼呢?所謂二元是指一個節點最多只有兩個子節點。從下圖可以看到一個二元搜尋樹之中,一個節點的左子節點 (或整個左子節點所包含的子樹) 的值,一定都小於節點的值,而右子節點 (或整個右子節點所包含的子樹)的值,一定都大於節點的值。所以一個二元搜尋樹內的節點是有順序關係的,所以用在搜尋、排序等等情境,或進而被用來發展其他資料結構。更詳細的細節可以參考這裡

From Wiki

那麼接下來就讓我們看看這四個語言要怎麼實作 BST 吧!GoGo!


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))

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)
height = get_height(root)
print(height)
  • 跟在建 Linked list 的 Node 有點像,只是在 BST 中的每個 Node 有兩個子節點,所以會有 leftright 來分別指到左子節點和右子節點,另外當然也有 data 的部分囉!
  • 插入新節點的 Function 是 insert,概念上是從 root 開始,假使一開始連 root 都沒有就直接生成一個新的 Node (Node(data))。如果輸入的值小於等於 root 的值就以遞迴的方式,呼叫 insert 但此時給的是左子樹的 Node 來視為這個 insert 的 root。完成之後記得將 root 的左子樹設成剛才遞迴得到的左子樹的根 (root.left = cur)。假設輸入的值大於 root 的值,一樣也是用遞迴的方式,只是這時候 insert 的是右子樹囉!
  • 另外 get_height 這個 Function 是告訴我們這個 BST 的樹有多高,也就是最深的子樹有幾個 Edge 高,以上面第二個圖為例,就是 3。概念上是從 root 出發,看左子樹和右子樹誰比較高。為了能夠有遞迴的效果,我們讓即使只有一個節點也有高度 1,但是只要左右子節點是 None 的話,就要 -1 扣回來囉!

上一篇
[Day 21] 什麼類型都可以
下一篇
[Day 23] 再好好看看這棵樹
系列文
30 天把自己榨好榨滿的四週四語言大挑戰!30

尚未有邦友留言

立即登入留言