🏝用Python來實現 Binary Tree 二元樹
閱讀時間約 1 分鐘
接著來進入圖論的重點之一，Tree與Binary Tree。
二元樹（Binary Tree）是一種樹狀數據結構，其中每個節點最多有兩個子節點，通常稱為左子節點和右子節點。這些子節點可以是實體節點 或 空節點。
二元樹是其他進階樹的基礎，可延伸推廣到Binary Search Tree二元搜索樹、Heap堆、Huffman Tree霍夫曼樹...等等。
定義
二元樹一種樹狀數據結構，其中每個節點最多有兩個子節點，通常稱為左子節點和右子節點。這些子節點可以是實體節點 或 空節點。
- 根節點（Root Node）：樹的頂部節點。
- 葉節點（Leaf Node）：沒有子節點的節點。
- 內部節點（Internal Node）：至少有一個子節點的節點。
- 深度（Depth）：從根節點到葉節點的最長路徑上的節點數。
一開始，初始化時是一顆空樹，隨著資料的增加而成為一顆擁有實體節點的二元樹。
兩種特殊形式
- Complete Binary Tree
除了最後一層外，每一層的節點都是滿的，且最後一層的節點從左到右依次排列。
- Full Binary Tree
所有內部節點都有兩個子節點，最後一層皆為葉子節點。
優點
1.可以根據需求動態延伸或縮短，有效利用記憶體空間。
缺點
1.不支援random acess，不支援BinaryTree[ index ] 這種操作。
2.如果要搜尋或者訪問某個元素，一定要從根節點開始拜訪(或搜尋)整顆樹。
run-time成本相當昂貴。
3.只能單向訪問，相當於單行道，只能從上到下(從根節點到葉子節點)訪問。
節點Node的Python實作
class Node:
def __init__(self, data):
# 資料欄位
self.data = data
# 左子節點
self.left = None
# 右子節點
self.right = None
Binary Tree的class定義 與 建構子(初始化的函式)
class BinaryTree:
def __init__(self):
# 初始化時是一顆空樹
self.root = None
Binary Tree常見的操作
1.插入節點 insert(data)
如果當下節點為空，則放入當下的位置。
如果左子節點為空，則放入左子節點。
如果右子節點為空，則放入右子節點。
如果左子節點、右子節點都已經使用，則往下一層尋找空位。
(補充: Binary Tree並無硬性規定插入方式，讀者可自行定義)
時間複雜度: O(n) 線性時間
def insert(self, data):
if self.root == None:
self.root = Node(data)
else:
self._insert(self.root, data)
return
def _insert(self, cur_node, data):
if cur_node == None:
# 如果當下節點為空，則放入當下的位置。
cur_node = Node(data)
elif cur_node.left == None:
# 如果左子節點為空，則放入左子節點。
cur_node.left = Node(data)
elif cur_node.right == None:
# 如果右子節點為空，則放入右子節點。
cur_node.right = Node(data)
# 如果左子節點、右子節點都已經使用，則往下一層尋找空位。
elif cur_node.left.left is None or cur_node.left.right is None:
self._insert(cur_node.left, data)
elif cur_node.right.left is None or cur_node.right.right is None:
self._insert(cur_node.right, data)
else:
self._insert(cur_node.left, data)
return
2.搜尋某個節點值 search(data)
從根節點開始往下搜尋，查看某個節點值是否存在。
如果有，返回該節點。
如果沒有，返回None。
時間複雜度: O(n) 線性時間
def search(self, data):
return self._search(self.root, data)
def _search(self, cur_node, data):
if not cur_node:
return None
if cur_node.data == data:
return cur_node
else:
return self._search(cur_node.left, data) or self._search(cur_node.right, data)
3.刪除指定的節點 delete( data )
從根節點開始往下搜尋，查看某個節點值是否存在。
如果有，刪除該節點，填補空缺，返回被刪除的節點。
如果沒有，返回None。
(補充: Binary Tree並無硬性規定填補空缺的方式，讀者可自行定義)
時間複雜度: O(n) 線性時間
def delete(self, data):
return self._deleteNode(self.root, data)
def _deleteNode(self, cur_node, data):
if not cur_node:
return None
if cur_node.data != data:
return self._deleteNode( cur_node.left, data ) or self._deleteNode( cur_node.right, data )
else:
# 當下就是要被刪除的節點
if (not cur_node.left) or (not cur_node.right):
# 至少有一個子節點是空的
# 由存在的那個子節點 或者 None 填補刪除後的空缺
cur_node = cur_node.left if cur_node.left else cur_node.right
else:
# 兩個子節點都存在
# 由右子樹最左下角的節點 填補刪除後的空缺
replace = cur_node.right
while replace.left:
replace = replace.left
cur_node.data = replace.data
cur_node.right = self._deleteNode( cur_node.right, replace.data )
return Node(data)
4.取得樹的深度 depth()
從根節點開始往葉子節點拜訪，取得最長路徑上的節點數 = 樹的深度。
時間複雜度: O(log n) 對數時間
def depth(self):
return self._depth(self.root)
def _depth(self, cur_node):
if not cur_node:
return 0
return 1 + max( self._depth(cur_node.left), self._depth(cur_node.right) )
5.樹的中序拜訪 inorder traversal
先拜訪左子樹、接著拜訪當下節點、最後拜訪右子樹。
依此定義，遞迴拜訪整顆樹。
時間複雜度: O(n) 線性時間
def inorder(self):
self._inorder(self.root)
return
def _inorder(self, cur_node):
if cur_node:
self._inorder(cur_node.left)
print(str(cur_node.data) + "->", end='')
self._inorder(cur_node.right)
return
6.樹的逐層拜訪 level-order traversal
從樹根開始，逐層由上往下拜訪每一層，每一層由左往右拜訪每個節點。
時間複雜度: O(n) 線性時間
def levelorder(self):
bfs_q = [self.root] if self.root else []
while bfs_q:
next_level = []
for cur_node in bfs_q:
print(str(cur_node.data) + "->", end='')
if cur_node.left:
next_level.append(cur_node.left)
if cur_node.right:
next_level.append(cur_node.right)
bfs_q = next_level
return
測試範例
完整的Binary Tree實作和程式碼
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def insert(self, data):
if self.root == None:
self.root = Node(data)
else:
self._insert(self.root, data)
return
def _insert(self, cur_node, data):
if cur_node == None:
cur_node = Node(data)
elif cur_node.left == None:
cur_node.left = Node(data)
elif cur_node.right == None:
cur_node.right = Node(data)
elif cur_node.left.left is None or cur_node.left.right is None:
self._insert(cur_node.left, data)
elif cur_node.right.left is None or cur_node.right.right is None:
self._insert(cur_node.right, data)
else:
self._insert(cur_node.left, data)
return
def inorder(self):
self._inorder(self.root)
return
def _inorder(self, cur_node):
if cur_node:
self._inorder(cur_node.left)
print(str(cur_node.data) + "->", end='')
self._inorder(cur_node.right)
return
def levelorder(self):
bfs_q = [self.root] if self.root else []
while bfs_q:
next_level = []
for cur_node in bfs_q:
print(str(cur_node.data) + "->", end='')
if cur_node.left:
next_level.append(cur_node.left)
if cur_node.right:
next_level.append(cur_node.right)
bfs_q = next_level
return
def search(self, data):
return self._search(self.root, data)
def _search(self, cur_node, data):
if not cur_node:
return None
if cur_node.data == data:
return cur_node
else:
return self._search(cur_node.left, data) or self._search(cur_node.right, data)
def delete(self, data):
return self._deleteNode(self.root, data)
def _deleteNode(self, cur_node, data):
if not cur_node:
return None
if cur_node.data != data:
return self._deleteNode( cur_node.left, data ) or self._deleteNode( cur_node.right, data )
else:
# 當下就是要被刪除的節點
if (not cur_node.left) or (not cur_node.right):
# 至少有一個子節點是空的
# 由存在的那個子節點 或者 None 填補刪除後的空缺
cur_node = cur_node.left if cur_node.left else cur_node.right
else:
# 兩個子節點都存在
# 由右子樹最左下角的節點 填補刪除後的空缺
replace = cur_node.right
while replace.left:
replace = replace.left
cur_node.data = replace.data
cur_node.right = self._deleteNode( cur_node.right, replace.data )
return Node(data)
def depth(self):
return self._depth(self.root)
def _depth(self, cur_node):
if not cur_node:
return 0
return 1 + max( self._depth(cur_node.left), self._depth(cur_node.right) )
def test():
tree = BinaryTree()
for i in range(1, 11):
print(f"insert {i}")
tree.insert(i)
print("\nSearch 5:")
res = tree.search(5)
if res:
print(res.data)
else:
print("None")
print("\nInorder traversal:")
tree.inorder()
print()
print("\nLevel-order traversal:")
tree.levelorder()
print()
print("\nDelete 8:")
res = tree.delete(8)
if res:
print(res.data)
else:
print("None")
print("\nDelete 11:")
res = tree.delete(11)
if res:
print(res.data)
else:
print("None")
print(f"\nTree depth = {tree.depth()}" )
if __name__ == "__main__":
test()
測試輸出
insert 1
insert 2
insert 3
insert 4
insert 5
insert 6
insert 7
insert 8
insert 9
insert 10
Search 5:
5
Inorder traversal:
8->4->9->2->10->5->1->6->3->7->
Level-order traversal:
1->2->3->4->5->6->7->8->9->10->
Delete 8:
8
Delete 11:
None
Tree depth = 4
結語
其實Tree就是Node的組合與推廣，每個節點最多可以有兩個子節點的樹狀資料結構。
讀者可以透過紙筆追蹤演算法和程式執行邏輯，測試幾個簡單的小範例，
會有更深刻的了解和體會！
Binary Tree相關的演算法練習題與詳解
一題多解 二元樹的右側視角Binary Tree Right Side View_Leetcode #199_精選75題
🎄圖論應用: 二元樹的後序拜訪 Binary Tree Postorder Traversal_LC #145
圖論應用題 驗證二元樹節點 Validate Binary Tree Nodes_Leetcode #1361
BFS 經典入門題 Binary Tree Level Order Traversal II Leetcode #107
BFS 經典入門題 Binary Tree Level Order Traversal_Leetcode #102
經典圖論面試題 Invert Binary Tree_Leetcode #226
使用DFS 模板 + 基礎圖論題目 Binary Tree Paths Leetcode #257
86會員
425內容數
由有業界實戰經驗的演算法工程師，
手把手教你建立解題的框架，
一步步寫出高效、清晰易懂的解題答案。
著重在讓讀者啟發思考、理解演算法，熟悉常見的演算法模板。
深入淺出地介紹題目背後所使用的演算法意義，融會貫通演算法與資料結構的應用。
在幾個經典的題目融入一道題目的多種解法，或者同一招解不同的題目，擴展廣度，並加深印象。
留言0
查看全部
你可能也想看
Google News 追蹤
這個秋，Chill 嗨嗨！穿搭美美去賞楓，裝備款款去露營⋯⋯你的秋天怎麼過？秋日 To Do List 等你分享！
秋季全站徵文，我們準備了五個創作主題，參賽還有機會獲得「火烤兩用鍋」，一起來看看如何參加吧～
說來慚愧，我一直到疫情期間不能出國的時候，人生才第一次去澎湖。選了暑假去，剛好碰上延期的花火節，碰到馬公機場史上人數最多的一天！關於澎湖景點、美食推薦，網路上的資訊很多，我自己在做功課的時候覺得資訊滿混亂的，本篇就根據我們此行的經驗，為大家解答規劃時的疑惑💡
距離香港不遠的西貢，藏有奇形怪石的美麗景色。逃離城市的喧囂，置身於大自然間，感受到生活的美好。沿途遊覽不同小島，參觀特色景點，欣賞石頭之美，是一次難忘的環島之旅。
賣屋買屋我知道，讓你成交沒煩惱！
本週和大家分享我們最常最常碰到的客戶提問之一：「為什麼資料得公開？」
筆者可以細數一些顯而易見的好處，不過有一件事，是無論我們接下來如何改版、如何優化功能都無法再次為客戶提供的頭銜，即是第一批掛保證敢公開的時間戳記。
前陣子一位新北建案的經理和筆者分享，他很擔心 1
這之後在荒島的每個晚上，每當我想要在腦中探尋、找回更多過往情境的記憶時，就會划起木筏來到這個被卡在海蝕洞的貨櫃屋裡。今晚，我想來點......
屋內那個未曾消散、令人不適的視線，只是研究單位監控我的方式嗎？我感覺，那視線好像來自更遙遠的地方，一個不同的維度。此時此刻身處於荒島的我，會不會只是個虛構的概念？利用某些影像、聲音、甚至文字捏成人形，被人們透過面前發著幽光的螢幕，不發一語地盯著看呢？
《Desert Island Discs》是英國BBC Radio 4 的一個廣播節目，自1942年起首播，至今已超過70年。這個節目情境是訪問節目來賓，如果他即將要長居荒島，與世隔絕，請選擇8張黑膠唱片、1本書、與1項奢侈品同行......
網路謠言滿天飛，用更客觀的科學知識強身健體吧！
方格子健康月，匯集各大領域的健康保健專題，日常防護、皮膚保養、身體排毒、心理療癒——即刻啟動閱讀，讓你從裡到外補充滿滿能量，照顧好自己的身心靈！4/30前訂閱或購買健康月精選專題，輸入折扣碼health2020，精選專題全面8折起。
方格子無廣告簡潔的介面非常適合用關燈模式進行閱讀或創作
身為一個宅宅工程師，螢幕打開應該就是要黑黑 der 才算是稱職（？）
方格子的介面因為沒有廣告也夠簡單，因此特別適合用關燈模式進行創作或是閱讀，在 Chrome 上面有許多外掛可以使用，新版的 Chrome 也可以選擇黑暗模式
這個秋，Chill 嗨嗨！穿搭美美去賞楓，裝備款款去露營⋯⋯你的秋天怎麼過？秋日 To Do List 等你分享！
秋季全站徵文，我們準備了五個創作主題，參賽還有機會獲得「火烤兩用鍋」，一起來看看如何參加吧～
說來慚愧，我一直到疫情期間不能出國的時候，人生才第一次去澎湖。選了暑假去，剛好碰上延期的花火節，碰到馬公機場史上人數最多的一天！關於澎湖景點、美食推薦，網路上的資訊很多，我自己在做功課的時候覺得資訊滿混亂的，本篇就根據我們此行的經驗，為大家解答規劃時的疑惑💡
距離香港不遠的西貢，藏有奇形怪石的美麗景色。逃離城市的喧囂，置身於大自然間，感受到生活的美好。沿途遊覽不同小島，參觀特色景點，欣賞石頭之美，是一次難忘的環島之旅。
賣屋買屋我知道，讓你成交沒煩惱！
本週和大家分享我們最常最常碰到的客戶提問之一：「為什麼資料得公開？」
筆者可以細數一些顯而易見的好處，不過有一件事，是無論我們接下來如何改版、如何優化功能都無法再次為客戶提供的頭銜，即是第一批掛保證敢公開的時間戳記。
前陣子一位新北建案的經理和筆者分享，他很擔心 1
這之後在荒島的每個晚上，每當我想要在腦中探尋、找回更多過往情境的記憶時，就會划起木筏來到這個被卡在海蝕洞的貨櫃屋裡。今晚，我想來點......
屋內那個未曾消散、令人不適的視線，只是研究單位監控我的方式嗎？我感覺，那視線好像來自更遙遠的地方，一個不同的維度。此時此刻身處於荒島的我，會不會只是個虛構的概念？利用某些影像、聲音、甚至文字捏成人形，被人們透過面前發著幽光的螢幕，不發一語地盯著看呢？
《Desert Island Discs》是英國BBC Radio 4 的一個廣播節目，自1942年起首播，至今已超過70年。這個節目情境是訪問節目來賓，如果他即將要長居荒島，與世隔絕，請選擇8張黑膠唱片、1本書、與1項奢侈品同行......
網路謠言滿天飛，用更客觀的科學知識強身健體吧！
方格子健康月，匯集各大領域的健康保健專題，日常防護、皮膚保養、身體排毒、心理療癒——即刻啟動閱讀，讓你從裡到外補充滿滿能量，照顧好自己的身心靈！4/30前訂閱或購買健康月精選專題，輸入折扣碼health2020，精選專題全面8折起。
方格子無廣告簡潔的介面非常適合用關燈模式進行閱讀或創作
身為一個宅宅工程師，螢幕打開應該就是要黑黑 der 才算是稱職（？）
方格子的介面因為沒有廣告也夠簡單，因此特別適合用關燈模式進行創作或是閱讀，在 Chrome 上面有許多外掛可以使用，新版的 Chrome 也可以選擇黑暗模式