使用二叉搜索树进行排序的 Python 程序
pythonserver side programmingprogramming更新于 2023/12/23 11:47:00
当需要对二叉搜索树进行排序时，会创建一个类，并在其中定义执行插入元素和执行中序遍历等操作的方法。
下面是相同的演示 −
示例
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’创建了具有所需属性的类。
它有一个‘init’函数，用于将‘left’、‘right’和‘parent’节点分配给‘None’。
定义了另一个名为‘insert_elem’的方法，用于帮助将节点添加到树中。
定义了另一个名为‘inorder_traversal’的方法，用于帮助对树执行中序遍历。
定义了另一个名为‘BinSearchTree’的类。
它将根设置为‘None’。
它有一个名为‘inorder_traversal’的方法可帮助对树执行中序遍历。
定义了另一个名为‘add_val’的方法，可帮助向树中添加节点。
创建‘BinSearchTree’的一个实例。
用户获取数字列表。
使用此方法创建一棵树。
对列表进行排序，并执行中序遍历。
相关输出显示在控制台上。
