溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容主要講解“python如何實現二叉搜索樹”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“python如何實現二叉搜索樹”吧!
樹不同于鏈表或哈希表，是一種非線性數據結構，樹分為二叉樹、二叉搜索樹、B樹、B+樹、紅黑樹等等。
樹是一種數據結構，它是由n個有限節點組成的一個具有層次關系的集合。用圖片來表示的話，可以看到它很像一棵倒掛著的樹。因此我們將這類數據結構統稱為樹，樹根在上面，樹葉在下面。一般的樹具有以下特點：
每個節點有0個或者多個子節點
沒有父節點的節點被稱為根節點
每個非根節點有且只有一個父節點
每個子結點都可以分為多個不相交的子樹
二叉樹的定義是：每個節點最多有兩個子節點。即每個節點只能有以下四種情況：
左子樹和右子樹均為空
只存在左子樹
只存在右子樹
左子樹和右子樹均存在
二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質的二叉樹:
若它的左子樹不為空，則左子樹上所有節點的值都小于根節點的值 若它的右子樹不為空，則右子樹上所有節點的值都大于根節點的值
它的左右子樹也分別為二叉搜索樹
通過定義一個節點類，包含節點值、左右子節點等屬性，然后通過遞歸函數實現插入、查找、刪除等操作。代碼示例如下：
class Node: def __init__(self, data): self.data = data self.left = None self.right = None class BST: def __init__(self): self.root = None def insert(self, value): if self.root is None: self.root = Node(value) else: self._insert(value, self.root) def _insert(self, value, node): if value < node.data: if node.left is None: node.left = Node(value) else: self._insert(value, node.left) elif value > node.data: if node.right is None: node.right = Node(value) else: self._insert(value, node.right) def search(self, value): if self.root is None: return False else: return self._search(value, self.root) def _search(self, value, node): if node is None: return False elif node.data == value: return True elif value < node.data: return self._search(value, node.left) else: return self._search(value, node.right) def delete(self, value): if self.root is None: return False else: self.root = self._delete(value, self.root) def _delete(self, value, node): if node is None: return node elif value < node.data: node.left = self._delete(value, node.left) elif value > node.data: node.right = self._delete(value, node.right) else: if node.left is None and node.right is None: del node return None elif node.left is None: temp = node.right del node return temp elif node.right is None: temp = node.left del node return temp else: temp = self._find_min(node.right) node.data = temp.data node.right = self._delete(temp.data, node.right) return node def _find_min(self, node): while node.left is not None: node = node.left return node
通過使用一個列表來存儲二叉搜索樹的元素，然后通過列表中元素的位置關系來實現插入、查找、刪除等操作。代碼示例如下：
class BST: def __init__(self): self.values = [] def insert(self, value): if len(self.values) == 0: self.values.append(value) else: self._insert(value, 0) def _insert(self, value, index): if value < self.values[index]: left_child_index = 2 * index + 1 if left_child_index >= len(self.values): self.values.extend([None] * (left_child_index - len(self.values) + 1)) if self.values[left_child_index] is None: self.values[left_child_index] = value else: self._insert(value, left_child_index) else: right_child_index = 2 * index + 2 if right_child_index >= len(self.values): self.values.extend([None] * (right_child_index - len(self.values) + 1)) if self.values[right_child_index] is None: self.values[right_child_index] = value else: self._insert(value, right_child_index) def search(self, value): if value in self.values: return True else: return False def delete(self, value): if value not in self.values: return False else: index = self.values.index(value) self._delete(index) return True def _delete(self, index): left_child_index = 2 * index + 1 right_child_index = 2 * index + 2 if left_child_index < len(self.values) and self.values[left_child_index] is not None: self._delete(left_child_index) if right_child_index < len(self.values) and self.values[right_child_index] is not None: self
其中字典的鍵表示節點值，字典的值是一個包含左右子節點的字典。代碼示例如下：
def insert(tree, value):
if not tree:
return {value: {}}
elif value < list(tree.keys())[0]:
tree[list(tree.keys())[0]] = insert(tree[list(tree.keys())[0]], value)
else:
tree[list(tree.keys())[0]][value] = {}
return tree
def search(tree, value):
if not tree:
return False
elif list(tree.keys())[0] == value:
return True
elif value < list(tree.keys())[0]:
return search(tree[list(tree.keys())[0]], value)
else:
return search(tree[list(tree.keys())[0]].get(value), value)
def delete(tree, value):
if not search(tree, value):
return False
else:
if list(tree.keys())[0] == value:
if not tree[list(tree.keys())[0]]:
del tree[list(tree.keys())[0]]
elif len(tree[list(tree.keys())[0]]) == 1:
tree[list(tree.keys())[0]] = list(tree[list(tree.keys())[0]].values())[0]
else:
min_key = min(list(tree[list(tree.keys())[0]+1].keys()))
tree[min_key] = tree[list(tree.keys())[0]+1][min_key]
tree[min_key][list(tree.keys())[0]] = tree[list(tree.keys())[0]]
del tree[list(tree.keys())[0]]
elif value < list(tree.keys())[0]:
tree[list(tree.keys())[0]] = delete(tree[list(tree.keys())[0]], value)
else:
tree[list(tree.keys())[0]][value] = delete(tree[list(tree.keys())[0]].get(value), value)
return tree由于字典是無序的，因此該實現方式可能會導致二叉搜索樹不平衡，影響插入、查找和刪除操作的效率。
使用堆棧（Stack）可以實現一種簡單的二叉搜索樹，可以通過迭代方式實現插入、查找、刪除等操作。具體實現過程如下：
定義一個節點類，包含節點值、左右子節點等屬性。
定義一個堆棧，初始時將根節點入棧。
當棧不為空時，取出棧頂元素，并對其進行操作：如果要插入的值小于當前節點值，則將要插入的值作為左子節點插入，并將左子節點入棧；如果要插入的值大于當前節點值，則將要插入的值作為右子節點插入，并將右子節點入棧；如果要查找或刪除的值等于當前節點值，則返回或刪除該節點。
操作完成后，繼續從堆棧中取出下一個節點進行操作，直到堆棧為空。
需要注意的是，在這種實現方式中，由于使用了堆棧來存儲遍歷樹的過程，因此可能會導致內存占用較高。另外，由于堆棧的特性，這種實現方式只能支持深度優先遍歷（Depth-First Search，DFS），不能支持廣度優先遍歷（Breadth-First Search，BFS）。
以下是偽代碼示例：
class Node: def __init__(self, data): self.data = data self.left = None self.right = None def insert(root, value): if not root: return Node(value) stack = [root] while stack: node = stack.pop() if value < node.data: if node.left is None: node.left = Node(value) break else: stack.append(node.left) elif value > node.data: if node.right is None: node.right = Node(value) break else: stack.append(node.right) def search(root, value): stack = [root] while stack: node = stack.pop() if node.data == value: return True elif value < node.data and node.left: stack.append(node.left) elif value > node.data and node.right: stack.append(node.right) return False def delete(root, value): if root is None: return None if value < root.data: root.left = delete(root.left, value) elif value > root.data: root.right = delete(root.right, value) else: if root.left is None: temp = root.right del root return temp elif root.right is None: temp = root.left del root return temp else: temp = root.right while temp.left is not None: temp = temp.left root.data = temp.data root.right = delete(root.right, temp.data) return root
到此，相信大家對“python如何實現二叉搜索樹”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
