欢迎访问宙启技术站
智能推送

使用Python实现二叉搜索树的插入和搜索功能。

发布时间:2023-12-04 13:50:20

二叉搜索树(Binary Search Tree,简称BST)是一种常见的数据结构,它是一棵二叉树,并满足以下性质:

- 对于树中的任意节点,其左子树中的所有节点的值都小于该节点的值。

- 对于树中的任意节点,其右子树中的所有节点的值都大于该节点的值。

- 左子树和右子树也是二叉搜索树。

下面是使用Python实现二叉搜索树的插入和搜索功能的代码示例:

# 定义二叉搜索树的节点类
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# 定义二叉搜索树类
class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    # 插入节点
    def insert(self, value):
        if not self.root:
            self.root = Node(value)
        else:
            self._insert(self.root, value)
    
    def _insert(self, node, value):
        if value < node.value:
            if node.left:
                self._insert(node.left, value)
            else:
                node.left = Node(value)
        else:
            if node.right:
                self._insert(node.right, value)
            else:
                node.right = Node(value)
    
    # 搜索节点
    def search(self, value):
        if self.root:
            return self._search(self.root, value)
        else:
            return False
    
    def _search(self, node, value):
        if not node:
            return False
        if node.value == value:
            return True
        elif value < node.value:
            return self._search(node.left, value)
        else:
            return self._search(node.right, value)

使用示例:

bst = BinarySearchTree()
# 插入节点
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(1)
bst.insert(4)
bst.insert(6)
bst.insert(8)

# 搜索节点
print(bst.search(6))  # 输出True
print(bst.search(10))  # 输出False

以上示例中,我们创建了一棵二叉搜索树,并插入了一些节点进行测试。最后使用搜索功能来查找特定的节点是否存在于树中。