Python程序查找二叉搜索树中最小和最大元素

什么是二叉搜索树

二叉搜索树（Binary Search Tree，BST）是一棵为空树或具有以下性质的二叉树：

左子树上所有节点的值均小于它的根节点的值。
右子树上所有节点的值均大于它的根节点的值。
左右子树分别为二叉搜索树。

这里使用Python实现二叉搜索树的节点：

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

Python程序查找二叉搜索树中最小元素

二叉搜索树中最小元素即为左子树最左下方的叶子节点。我们可以按照以下方法查找：

若当前节点为None，返回None。
若当前节点存在左子树，一直往左子树查找，直到找到最左下方的叶子节点。
若当前节点不存在左子树，则返回当前节点的值。

下面是Python程序实现：

def findMin(root):
    if not root:
        return None
    while root.left:
        root = root.left
    return root.val

首先对当前节点进行判断，若当前节点不存在，返回None；若当前节点存在左子树，一直往左子树查找，直到找到最左下方的叶子节点；若当前节点不存在左子树，则返回当前节点的值。可以使用以下的代码测试：

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)

print("最小元素为：", findMin(root))

结果应该为：

最小元素为： 1

Python程序查找二叉搜索树中最大元素

二叉搜索树中最大元素即为右子树最右下方的叶子节点。我们可以按照以下方法查找：

若当前节点为None，返回None。
若当前节点存在右子树，一直往右子树查找，直到找到最右下方的叶子节点。
若当前节点不存在右子树，则返回当前节点的值。

下面是Python程序实现：

def findMax(root):
    if not root:
        return None
    while root.right:
        root = root.right
    return root.val

首先对当前节点进行判断，若当前节点不存在，返回None；若当前节点存在右子树，一直往右子树查找，直到找到最右下方的叶子节点；若当前节点不存在右子树，则返回当前节点的值。可以使用以下的代码测试：

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)

print("最大元素为：", findMax(root))

结果应该为：