python實作二元搜尋樹的方法有哪些

樹的介紹

樹不同於鍊錶或雜湊表，是一種非線性資料結構，樹分為二元樹、二元搜尋樹、B樹、B 樹、紅黑樹等等。

樹是一種資料結構，它是由n個有限節點組成的一個具有層次關係的集合。用圖片來表示的話，可以看到它很像一棵倒掛著的樹。因此我們將這類資料結構統稱為樹，樹根在上面，樹葉在下面。一般的樹有以下特點：

• 每個節點有0個或多個子節點

• 沒有父節點的節點稱為根節點

• 每個非根節點有且只有一個父節點

• #每個子結點都可以分成多個不相交的子樹

二元樹的定義是：每個節點最多有兩個子節點。即每個節點只能有以下四種情況：

• 左子樹、右子樹皆為空

• ##只存在左子樹

• 只存在右子樹

• 左子樹和右子樹都存在

二元搜尋樹

二元搜尋樹又稱為二元排序樹，它或是一棵空樹，或是具有以下性質的二元樹:

• 若它的左子樹不為空，則左子樹上所有節點的值都小於根節點的值若它的右子樹不為空，則右子樹上所有節點的值都大於根節點的值

• 它的左右子樹也分別為二元搜尋樹

#列舉幾種Python中幾種常見的實作方式：

1.使用類別和遞歸函數實現

透過定義一個節點類，包含節點值、左右子節點等屬性，然後透過遞歸函數實現插入、查找、刪除等操作。程式碼範例如下：

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

2.使用清單實作

透過使用清單來儲存二元搜尋樹的元素，然後透過清單中元素的位置關係來實現插入、尋找、刪除等操作。程式碼範例如下：

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

3.使用字典實作

其中字典的鍵表示節點值，字典的值是一個包含左右子節點的字典。程式碼範例如下：

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

由於字典是無序的，因此此實作方式可能會導致二元搜尋樹不平衡，影響插入、尋找和刪除操作的效率。

4.使用堆疊實作

使用堆疊（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實作二元搜尋樹的方法有哪些的詳細內容。更多資訊請關注PHP中文網其他相關文章！