设计链式存储结构建立一颗二叉排序树

以下是建立一棵链式存储结构的二叉排序树的Python实现：

# 定义二叉树结点类
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# 插入结点函数
def insert(root, val):
    if not root:
        root = TreeNode(val)
    elif val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)
    return root

# 中序遍历函数（递增顺序）
def inorder(root):
    if root:
        inorder(root.left)
        print(root.val)
        inorder(root.right)

# 查找函数
def search(root, val):
    if not root:
        return False
    elif root.val == val:
        return True
    elif val < root.val:
        return search(root.left, val)
    else:
        return search(root.right, val)

# 逆序中序遍历函数（递减顺序）
def reverse_inorder(root):
    if root:
        reverse_inorder(root.right)
        print(root.val)
        reverse_inorder(root.left)

使用示例：

# 建立二叉排序树
root = None
nums = [5, 3, 7, 1, 9, 4, 6, 2, 8]
for num in nums:
    root = insert(root, num)

# 中序遍历输出递增顺序的结点值
print("递增顺序：")
inorder(root)

# 查找结点
key1 = 4
if search(root, key1):
    print(f"{key1} 找到了")
else:
    print(f"{key1} 没找到")

# 插入结点
key2 = 10
if not search(root, key2):
    root = insert(root, key2)

# 逆序中序遍历输出递减顺序的结点值
print("递减顺序：")
reverse_inorder(root)