数据结构二叉排序树课程设计

二叉排序树是一种特殊的二叉树，它的左子树中的所有节点的值都小于根节点的值，右子树中的所有节点的值都大于根节点的值。因此，二叉排序树的中序遍历结果是一个有序的序列。下面是一个简单的二叉排序树的课程设计：

1.定义二叉排序树的节点类

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

2.定义二叉排序树类

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

    # 插入节点
    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
        else:
            self._insert(val, self.root)

    def _insert(self, val, node):
        if val < node.val:
            if not node.left:
                node.left = TreeNode(val)
            else:
                self._insert(val, node.left)
        else:
            if not node.right:
                node.right = TreeNode(val)
            else:
                self._insert(val, node.right)

    # 查找节点
    def search(self, val):
        return self._search(val, self.root)

    def _search(self, val, node):
        if not node:
            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 delete(self, val):
        self._delete(val, self.root)

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

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

    # 中序遍历
    def inorder(self):
        res = []
        self._inorder(self.root, res)
        return res

    def _inorder(self, node, res):
        if not node:
            return
        self._inorder(node.left, res)
        res.append(node.val)
        self._inorder(node.right, res)

3.测试代码

bst = BST()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(1)
bst.insert(9)
print(bst.inorder()) # 输出：[1, 3, 5, 7, 9]
bst.delete(3)
print(bst.inorder()) # 输出：[1, 5, 7, 9]
print(bst.search(7)) # 输出：True
print(bst.search(4)) # 输出：False