使用二叉搜索树对 Python 程序进行排序

排序是计算机程序中经常用到的操作，对程序执行效率和结果准确性影响很大。二叉搜索树作为一种常用的数据结构，在排序算法中也有着广泛的应用。本文将介绍如何使用二叉搜索树对 Python 程序进行排序。

二叉搜索树简介

二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树，具有以下特点：

• 每个节点最多有两个子节点；
• 左子节点比父节点小，右子节点比父节点大。

由此可知，搜索树的根节点是整个树中最大的节点，同时由于其特殊性，搜索树对于查找、插入和删除操作的时间复杂度都是 O(logN) 级别，效率较高。

以下是一个简单的二叉搜索树数据结构定义。

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

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

首先定义一个节点类 TreeNode，其包含左右子节点和节点数值 val。然后再定义二叉搜索树类 BST，其包含根节点 root。

BST 的插入操作

二叉搜索树常用的操作有插入、查找和删除。下面我们将介绍如何实现 BST 的插入操作。

在 BST 中插入一个节点时，首先需要在 BST 中查找一个节点，将新节点插入到某个节点的左子节点或右子节点。

以下是 BST 插入操作的示例代码。

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


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

    def insertNode(self, node, val):
        if not node:
            return TreeNode(val)
        if val < node.val:
            node.left = self.insertNode(node.left, val)
        elif val > node.val:
            node.right = self.insertNode(node.right, val)
        return node

    def insert(self, val):
        self.root = self.insertNode(self.root, val)

其中方法 insertNode 用于插入一个节点，方法 insert 则用于将 val 插入 BST 中。

BST 的查找操作

二叉搜索树的查找操作也十分简单，即比较当前节点的值与待查找值的大小，如果相等则返回该节点，否则根据大小关系选择左子树或右子树递归查找。

以下是 BST 查找操作的示例代码。

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


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

    def insertNode(self, node, val):
        if not node:
            return TreeNode(val)
        if val < node.val:
            node.left = self.insertNode(node.left, val)
        elif val > node.val:
            node.right = self.insertNode(node.right, val)
        return node

    def insert(self, val):
        self.root = self.insertNode(self.root, val)

    def search(self, val):
        node = self.root
        while node:
            if val == node.val:
                return node
            elif val < node.val:
                node = node.left
            else:
                node = node.right
        return None

方法 search 将从根节点开始递归查找节点的值是否等于 val。如果等于则返回该节点，否则返回 None。

BST 的排序操作

二叉搜索树的排序操作可以通过中序遍历实现。中序遍历是一种先遍历左子树、再遍历根节点、最后遍历右子树的遍历方式，因为 BST 中节点的数值大小关系满足左小右大，因此中序遍历的结果是从小到大排列的。

以下是 BST 的中序遍历算法代码示例。

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


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

    def insertNode(self, node, val):
        if not node:
            return TreeNode(val)
        if val < node.val:
            node.left = self.insertNode(node.left, val)
        elif val > node.val:
            node.right = self.insertNode(node.right, val)
        return node

    def insert(self, val):
        self.root = self.insertNode(self.root, val)

    def search(self, val):
        node = self.root
        while node:
            if val == node.val:
                return node
            elif val < node.val:
                node = node.left
            else:
                node = node.right
        return None

    def inOrderTraversal(self, node):
        res = []
        if not node:
            return res
        res += self.inOrderTraversal(node.left)
        res.append(node.val)
        res += self.inOrderTraversal(node.right)
        return res

    def sort(self):
        return self.inOrderTraversal(self.root)

方法 inOrderTraversal 将对树进行中序遍历，并将结果存储在一个列表中返回。方法 sort 将返回 BST 中节点值的升序排列结果。

使用 BST 对 Python 对象进行排序

以上已经介绍了如何使用 BST 对数字进行排序。对于其他 Python 对象类型，我们可以扩展上述实现，让 BST 能够对其进行排序。

以下是可自定义排序的 BST 的示例代码。

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


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

    def insertNode(self, node, val):
        if not node:
            return TreeNode(val)
        if self.key(val) < self.key(node.val):
            node.left = self.insertNode(node.left, val)
        elif self.key(val) > self.key(node.val):
            node.right = self.insertNode(node.right, val)
        return node

    def insert(self, val):
        self.root = self.insertNode(self.root, val)

    def search(self, val):
        node = self.root
        while node:
            if val == node.val:
                return node
            elif self.key(val) < self.key(node.val):
                node = node.left
            else:
                node = node.right
        return None

    def inOrderTraversal(self, node):
        res = []
        if not node:
            return res
        res += self.inOrderTraversal(node.left)
        res.append(node.val)
        res += self.inOrderTraversal(node.right)
        return res

    def sort(self):
        return self.inOrderTraversal(self.root)

与之前的 BST 实现相比，只需增加一个参数 key 来指定对象的排序规则。方法 insertNode 和 search 将根据 key 来比较节点的大小关系，从而实现对对象的排序。

例如，我们可以使用如下方式来定义一个人员类及其排序规则：

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __repr__(self):
        return f'Person({self.name}, {self.age})'

def sort_by_name(p):
    return p.name

def sort_by_age(p):
    return p.age

以按照姓名或年龄对人员进行排序。以下是使用 BST 对人员进行排序的示例代码。

bst_name = BST(key=sort_by_name)
bst_name.insert(Person('Jack', 20))
bst_name.insert(Person('Tony', 18))
bst_name.insert(Person('Tom', 22))
bst_name.insert(Person('Alice', 19))

print(bst_name.sort())  # [Person(Alice, 19), Person(Jack, 20), Person(Tom, 22), Person(Tony, 18)]

bst_age = BST(key=sort_by_age)
bst_age.insert(Person('Jack', 20))
bst_age.insert(Person('Tony', 18))
bst_age.insert(Person('Tom', 22))
bst_age.insert(Person('Alice', 19))

print(bst_age.sort())  # [Person(Tony, 18), Person(Alice, 19), Person(Jack, 20), Person(Tom, 22)]

结论

本文介绍了如何使用 Python 实现一个二叉搜索树（BST），并使用 BST 对数字和对象进行排序。通过 BST 的特殊性，排序操作的时间复杂度为 O(logN)，效率较高。此外，BST 在查找和删除操作中也有广泛应用，是一个十分实用的数据结构。