使用二叉搜索树进行排序的 Python 程序
当需要对二叉搜索树进行排序时，会创建一个类，并在其中定义方法来执行诸如插入元素和执行中序遍历等操作。
以下是相同的演示-
示例
class BinSearchTreeNode:
def __init__(self, key):
self.key= key
self.left= None
self.right= None
self.parent= None
def insert_elem(self, node):
ifself.key> node.key:
ifself.leftis None:
self.left= node
node.parent= self
else:
self.left.insert_elem(node)
elifself.key<= node.key:
ifself.rightis None:
self.right= node
node.parent= self
else:
self.right.insert_elem(node)
def inorder_traversal(self):
ifself.leftis not None:
self.left.inorder_traversal()
print(self.key, end=' ')
ifself.rightis not None:
self.right.inorder_traversal()
class BinSearchTree:
def __init__(self):
self.root= None
def inorder_traversal(self):
ifself.rootis not None:
self.root.inorder_traversal()
def add_val(self, key):
new_node = BinSearchTreeNode(key)
ifself.rootis None:
self.root = new_node
else:
self.root.insert_elem(new_node)
my_instance = BinSearchTree()
my_list = input('Enter the list of numbers... ').split()
my_list = [int(x) for x in my_list]
for x in my_list:
my_instance.add_val(x)
print('Sorted list: ')
print(my_instance.inorder_traversal())输出结果Enter the list of numbers... 67 54 89 0 11 34 99 Sorted list: 0 11 34 54 67 89 99
解释
创建了具有必需属性的“BinSearchTreeNode”类。
它有一个“init”函数，用于将“左”、“右”和“父”节点分配给“无”。
定义了另一个名为“insert_elem”的方法，可帮助将节点添加到树中。
定义了另一个名为“inorder_traversal”的方法，它有助于在树上执行中序遍历。
定义了另一个名为“BinSearchTree”的类。
它将根设置为“无”。
它有一个名为“inorder_traversal”的方法，可以帮助在树上执行中序遍历。
定义了另一种名为“add_val”的方法，可帮助将节点添加到树中。
'BinSearchTree'的一个实例被创建。
号码列表由用户获取。
使用此创建一棵树。
对列表进行排序，并执行其中序遍历。
相关输出显示在控制台上。