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

在需要对二叉搜索树进行排序时，创建一个类，并定义在其中执行操作（如插入元素和执行中序遍历）的方法。

下面是相同内容的演示−

示例

class BinSearchTreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None

    def insert_elem(self, node):
        if self.key > node.key:
            if self.left is None:
                self.left = node
                node.parent = self
            else:
                self.left.insert_elem(node)
        elif self.key <= node.key:
            if self.right is None:
                self.right = node
                node.parent = self
            else:
                self.right.insert_elem(node)

    def inorder_traversal(self):
        if self.left is not None:
            self.left.inorder_traversal()
        print(self.key, end=' ')
        if self.right is not None:
            self.right.inorder_traversal()

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

    def inorder_traversal(self):
        if self.root is not None:
            self.root.inorder_traversal()

    def add_val(self, key):
        new_node = BinSearchTreeNode(key)
        if self.root is None:
            self.root = new_node
        else:
            self.root.insert_elem(new_node)

my_instance = BinSearchTree()

my_list = input('输入数字列表... ').split()
my_list = [int(x) for x in my_list]
for x in my_list:
    my_instance.add_val(x)
print('排序列表：')
print(my_instance.inorder_traversal())

输出

输入数字列表... 67 54 89 0 11 34 99
排序列表：
0 11 34 54 67 89 99

说明

• 创建具有所需属性的 ‘BinSearchTreeNode’ 类。

• 它有一个被用于将 ‘left’、‘right’ 和 ‘parent’ 节点赋值为 ‘None’ 的 ‘init’ 函数。

• 定义了另一个名为 ‘insert_elem’ 的方法，用于向树中添加节点。

• 定义了另一个名为 ‘inorder_traversal’ 的方法，用于在树中执行中序遍历。

• 定义了另一个名为 ‘BinSearchTree’ 的类。

• 它将根设置为 ‘None。

• 它有一个叫做 ‘inorder_traversal’ 的方法，用于在树中执行中序遍历。

• 定义了另一个名为 ‘add_val’ 的方法，用于向树中添加节点。

• 创建了 ‘BinSearchTree’ 的一个实例。

• 有一个用户提供的数字列表。

• 使用此创建了一个树。

• 对列表进行排序，并执行其中序遍历。

• 将相关输出显示在控制台上。