如何在Python中使用二叉查找树算法

2023-04-16 00:00:00 算法查找如何在

二叉查找树（Binary Search Tree）是一种基于二分搜索的数据结构，它是一棵二叉树，且满足以下性质：

左子树中所有节点的值均小于等于根节点的值；
右子树中所有节点的值均大于等于根节点的值；
左子树和右子树也是一棵二叉查找树；
每个节点最多有两个子节点。

二叉查找树的基本操作包括查找、插入和删除。具体操作步骤如下：

查找：从根节点开始，如果要查找的值等于当前节点的值，则查找成功；如果要查找的值小于当前节点的值，则在左子树中查找；如果要查找的值大于当前节点的值，则在右子树中查找。如果找不到要查找的值，则查找失败。
插入：从根节点开始，如果要插入的值等于当前节点的值，则插入失败；如果要插入的值小于当前节点的值，则在左子树中插入；如果要插入的值大于当前节点的值，则在右子树中插入。需要注意的是，插入新节点时，要保证插入后仍满足二叉查找树的性质。
删除：删除操作需要考虑三种情况：
- 要删除的节点没有子节点：直接删除该节点。
- 要删除的节点只有一个子节点：将该节点的子节点替换该节点，然后删除该节点。
- 要删除的节点有两个子节点：在该节点的右子树中找到最小节点，将该节点的值替换为最小节点的值，然后删除最小节点。

下面是Python实现二叉查找树算法的示例代码：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def search(self, val):
        return self._search(val, self.root)

    def _search(self, val, node):
        if node is None:
            return False
        elif node.val == val:
            return True
        elif val < node.val:
            return self._search(val, node.left)
        else:
            return self._search(val, node.right)

    def insert(self, val):
        self.root = self._insert(val, self.root)

    def _insert(self, val, node):
        if node is None:
            return TreeNode(val)
        elif val < node.val:
            node.left = self._insert(val, node.left)
        else:
            node.right = self._insert(val, node.right)
        return node

    def delete(self, val):
        self.root = self._delete(val, self.root)

    def _delete(self, val, node):
        if node is None:
            return None
        elif val < node.val:
            node.left = self._delete(val, node.left)
        elif val > node.val:
            node.right = self._delete(val, node.right)
        else:
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                min_node = self._find_min(node.right)
                node.val = min_node.val
                node.right = self._delete(min_node.val, node.right)
        return node

    def _find_min(self, node):
        while node.left is not None:
            node = node.left
        return node

    def inorder_traversal(self):
        res = []
        self._inorder_traversal(self.root, res)
        return res

    def _inorder_traversal(self, node, res):
        if node is not None:
            self._inorder_traversal(node.left, res)
            res.append(node.val)
            self._inorder_traversal(node.right, res)

上述代码中定义了TreeNode类和BST类，分别表示二叉查找树的节点和二叉查找树。BST类中定义了查找、插入、删除和中序遍历等操作的方法。具体实现细节可以看代码注释。下面是使用示例：

bst = BST()
bst.insert("pidancode.com")
bst.insert("python")
bst.insert("Algorithm")
bst.insert("data structure")
print(bst.search("python")) # True
print(bst.search("coding")) # False
bst.delete("Algorithm")
print(bst.inorder_traversal()) # ['data structure', 'pidancode.com', 'python']

相关文章