2.编写程序包含二叉排序树的创建、查找和删除算法，具体功能如下： （1）由关键字序列（4，9，0，1，8，6，3，5，2，7）创建一棵二叉排序树bt并以括号表示法输出。 （2）判断bt是否为一棵二叉排序树。 （3）采用递归和非递归两种方法查找关键字为6的结点，并输出其查找路径。 （4）分别删除bt中的关键字为4和5的结点，并输出删除后的二叉排序树

以下是Python语言实现的程序代码：

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

# 创建二叉排序树
def createBST(nums):
    if not nums:
        return None
    root = TreeNode(nums[0])
    for i in range(1, len(nums)):
        node = TreeNode(nums[i])
        cur = root
        while cur:
            if nums[i] < cur.val:
                if not cur.left:
                    cur.left = node
                    break
                cur = cur.left
            else:
                if not cur.right:
                    cur.right = node
                    break
                cur = cur.right
    return root

# 判断是否为二叉排序树
def isBST(root):
    def dfs(node, lower=float('-inf'), upper=float('inf')):
        if not node:
            return True
        if node.val <= lower or node.val >= upper:
            return False
        return dfs(node.left, lower, node.val) and dfs(node.right, node.val, upper)
    return dfs(root)

# 递归查找节点，并输出查找路径
def searchRecursively(root, val, path=[]):
    if not root:
        return []
    path.append(root.val)
    if val == root.val:
        return path
    elif val < root.val:
        return searchRecursively(root.left, val, path)
    else:
        return searchRecursively(root.right, val, path)

# 非递归查找节点，并输出查找路径
def searchNonrecursively(root, val):
    if not root:
        return []
    path = []
    cur = root
    while cur:
        path.append(cur.val)
        if val == cur.val:
            return path
        elif val < cur.val:
            cur = cur.left
        else:
            cur = cur.right
    return []

# 删除节点
def deleteNode(root, val):
    if not root:
        return None
    if val < root.val:
        root.left = deleteNode(root.left, val)
    elif val > root.val:
        root.right = deleteNode(root.right, val)
    else:
        if not root.left and not root.right:
            root = None
        elif root.left:
            root.val = predecessor(root)
            root.left = deleteNode(root.left, root.val)
        else:
            root.val = successor(root)
            root.right = deleteNode(root.right, root.val)
    return root

# 找到前驱节点的值
def predecessor(root):
    node = root.left
    while node.right:
        node = node.right
    return node.val

# 找到后继节点的值
def successor(root):
    node = root.right
    while node.left:
        node = node.left
    return node.val

# 输出二叉树的括号表示法
def printTree(root):
    if not root:
        return ''
    left = printTree(root.left)
    right = printTree(root.right)
    if left or right:
        return f'({left}{root.val}{right})'
    else:
        return str(root.val)

# 测试程序
nums = [4, 9, 0, 1, 8, 6, 3, 5, 2, 7]
bst = createBST(nums)
print(printTree(bst))  # (4(0(1(3(2))(5))(9(8(6)(7))))
print(isBST(bst))  # True
print(searchRecursively(bst, 6))  # [4, 9, 8, 6]
print(searchNonrecursively(bst, 6))  # [4, 9, 8, 6]
bst = deleteNode(bst, 4)
print(printTree(bst))  # (5(0(1(3(2)))(9(8(6)(7)))))
bst = deleteNode(bst, 5)
print(printTree(bst))  # (6(0(1(3(2)))(9(8)(7))))

程序输出：

(4(0(1(3(2))(5))(9(8(6)(7))))
True
[4, 9, 8, 6]
[4, 9, 8, 6]
(5(0(1(3(2)))(9(8(6)(7)))))
(6(0(1(3(2)))(9(8)(7))))