2024-08-30|閱讀時間 ‧ 約 22 分鐘

🏝用Python來實現 Binary Tree 二元樹

Dave Kim on Unsplash

接著來進入圖論的重點之一，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