使用一維串列來表示二元搜尋樹時，我們可以將樹的結構視為完全二元樹，並使用類似於「堆積」的方式進行存儲。這種表示方法將樹的節點按層序排成一維串列，節點之間的父子關係可以由索引計算得出。
一維串列的二元搜尋樹表示方式
在一維串列中：
- 根節點位於索引
0。 - 對於位於索引
i的節點：- 左子節點位於索引
2*i + 1。 - 右子節點位於索引
2*i + 2。 - 父節點位於索引
(i - 1) // 2。
- 左子節點位於索引
此方法的限制是，二元搜尋樹在某些情況下會變得非常稀疏（例如只有右子樹），導致需要大量空間來存儲空節點（通常設為 None），因此這種方法適合用於完全二元樹或樹較為平衡的情況。
(1) 插入 (Insert)
在二元搜尋樹中插入新值時，需要找到適合的位置。以下是使用一維串列模擬插入的過程：
插入函式
def insert(tree, value):
if not tree: # 若樹為空，則將值加入根節點
tree.append(value)
return tree
i = 0 # 從根節點開始
while i < len(tree):
if value < tree[i]: # 若值小於當前節點，則應插入左子樹
left_child = 2 * i + 1
if left_child >= len(tree):
tree.extend([None] * (left_child - len(tree) + 1))
if tree[left_child] is None:
tree[left_child] = value
return tree
else:
i = left_child
else: # 若值大於等於當前節點，則應插入右子樹
right_child = 2 * i + 2
if right_child >= len(tree):
tree.extend([None] * (right_child - len(tree) + 1))
if tree[right_child] is None:
tree[right_child] = value
return tree
else:
i = right_child
測試插入
# 建立並插入節點
bst = []
for value in [5, 3, 2, 7, 1, 6, 4]:
bst = insert(bst, value)
print("插入後的二元搜尋樹:", bst)
(2) 搜尋 (Search)
搜尋函式檢查一維串列中的特定數值是否存在，根據二元搜尋樹的規則沿著層序搜尋。
搜尋函式
def search(tree, value):
i = 0 # 從根節點開始
while i < len(tree) and tree[i] is not None:
if tree[i] == value:
return True
elif value < tree[i]: # 若值小於當前節點，搜尋左子樹
i = 2 * i + 1
else: # 若值大於當前節點，搜尋右子樹
i = 2 * i + 2
return False
測試搜尋
print("搜尋 5:", search(bst, 5)) # 預期 True
print("搜尋 2:", search(bst, 2)) # 預期 True
print("搜尋 8:", search(bst, 8)) # 預期 False
(3) 遍歷 (Traversal)
以下是前序、中序和後序遍歷函式，對應二元搜尋樹的遍歷順序。
前序遍歷 (Preorder Traversal)
def preorder_traversal(tree, i=0):
if i >= len(tree) or tree[i] is None:
return []
return [tree[i]] + preorder_traversal(tree, 2 * i + 1) + preorder_traversal(tree, 2 * i + 2)
print("前序遍歷:", preorder_traversal(bst)) # 預期 [5, 3, 2, 1, 4, 7, 6]
中序遍歷 (Inorder Traversal)
def inorder_traversal(tree, i=0):
if i >= len(tree) or tree[i] is None:
return []
return inorder_traversal(tree, 2 * i + 1) + [tree[i]] + inorder_traversal(tree, 2 * i + 2)
print("中序遍歷:", inorder_traversal(bst)) # 預期 [1, 2, 3, 4, 5, 6, 7]
後序遍歷 (Postorder Traversal)
def postorder_traversal(tree, i=0):
if i >= len(tree) or tree[i] is None:
return []
return postorder_traversal(tree, 2 * i + 1) + postorder_traversal(tree, 2 * i + 2) + [tree[i]]
print("後序遍歷:", postorder_traversal(bst)) # 預期 [1, 2, 4, 3, 6, 7, 5]
(4) 樹的高度 (Height)
樹的高度可以通過計算最深層次來實現。這裡使用遞迴求得最大深度。
def height(tree, i=0):
if i >= len(tree) or tree[i] is None:
return 0
left_height = height(tree, 2 * i + 1)
right_height = height(tree, 2 * i + 2)
return 1 + max(left_height, right_height)
print("樹的高度:", height(bst)) # 預期 4
(5) 樹的直徑（最大距離）
樹的直徑是樹中兩節點間的最大距離，可以用遞迴方式求取左右子樹高度和，然後取最大值。
直徑函式
def diameter(tree):
def _diameter_and_height(i):
if i >= len(tree) or tree[i] is None:
return 0, 0 # 返回 (高度, 直徑)
left_height, left_diameter = _diameter_and_height(2 * i + 1)
right_height, right_diameter = _diameter_and_height(2 * i + 2)
current_height = 1 + max(left_height, right_height)
current_diameter = left_height + right_height
max_diameter = max(current_diameter, left_diameter, right_diameter)
return current_height, max_diameter
_, tree_diameter = _diameter_and_height(0)
return tree_diameter
print("樹的直徑（最大距離）:", diameter(bst)) # 預期 4
完整統整程式碼
以下是完整程式碼，整合了上述所有功能：
# 插入新值
def insert(tree, value):
if not tree:
tree.append(value)
return tree
i = 0
while i < len(tree):
if value < tree[i]:
left_child = 2 * i + 1
if left_child >= len(tree):
tree.extend([None] * (left_child - len(tree) + 1))
if tree[left_child] is None:
tree[left_child] = value
return tree
else:
i = left_child
else:
right_child = 2 * i + 2
if right_child >= len(tree):
tree.extend([None] * (right_child - len(tree) + 1))
if tree[right_child] is None:
tree[right_child] = value
return tree
else:
i = right_child
# 搜尋特定值
def search(tree, value):
i = 0
while i < len(tree) and tree[i] is not None:
if tree[i] == value:
return True
elif value < tree[i]:
i = 2 * i + 1
else:
i = 2 * i + 2
return False
# 前序遍歷
def preorder_traversal(tree, i=0):
if i >= len(tree) or tree[i] is None:
return []
return [tree[i]] + preorder_traversal(tree, 2 * i + 1) + preorder_traversal(tree, 2 * i +
2)
# 中序遍歷
def inorder_traversal(tree, i=0):
if i >= len(tree) or tree[i] is None:
return []
return inorder_traversal(tree, 2 * i + 1) + [tree[i]] + inorder_traversal(tree, 2 * i + 2)
# 後序遍歷
def postorder_traversal(tree, i=0):
if i >= len(tree) or tree[i] is None:
return []
return postorder_traversal(tree, 2 * i + 1) + postorder_traversal(tree, 2 * i + 2) + [tree[i]]
# 計算樹高
def height(tree, i=0):
if i >= len(tree) or tree[i] is None:
return 0
left_height = height(tree, 2 * i + 1)
right_height = height(tree, 2 * i + 2)
return 1 + max(left_height, right_height)
# 計算樹的直徑
def diameter(tree):
def _diameter_and_height(i):
if i >= len(tree) or tree[i] is None:
return 0, 0
left_height, left_diameter = _diameter_and_height(2 * i + 1)
right_height, right_diameter = _diameter_and_height(2 * i + 2)
current_height = 1 + max(left_height, right_height)
current_diameter = left_height + right_height
max_diameter = max(current_diameter, left_diameter, right_diameter)
return current_height, max_diameter
_, tree_diameter = _diameter_and_height(0)
return tree_diameter
# 測試二元搜尋樹功能
bst = []
for value in [5, 3, 2, 7, 1, 6, 4]:
bst = insert(bst, value)
print("搜尋 5:", search(bst, 5)) # 預期 True
print("搜尋 2:", search(bst, 2)) # 預期 True
print("搜尋 8:", search(bst, 8)) # 預期 False
print("前序遍歷:", preorder_traversal(bst)) # 預期 [5, 3, 2, 1, 4, 7, 6]
print("中序遍歷:", inorder_traversal(bst)) # 預期 [1, 2, 3, 4, 5, 6, 7]
print("後序遍歷:", postorder_traversal(bst)) # 預期 [1, 2, 4, 3, 6, 7, 5]
print("樹的高度:", height(bst)) # 預期 4
print("樹的直徑（最大距離）:", diameter(bst)) # 預期 5
此程式實現了插入、搜尋、遍歷、計算樹高及樹直徑的所有功能，並以一維串列模擬了二元搜尋樹的結構。
沒有留言:
張貼留言