使用链表实现二叉树的 Python 程序
pythonserver side programmingprogramming更新于 2023/12/27 2:23:00
当需要使用链表实现二叉树数据结构时，需要定义一种设置根节点的方法、一种按序遍历的方法、一种在根节点左侧插入元素的方法、一种在根节点右侧插入元素的方法以及一种搜索值的方法。
下面是同样的演示 −
示例
class BinaryTree_structure:
def __init__(self, key=None):
self.key = key
self.left = None
self.right = None
def set_root(self, key):
self.key = key
def in_order_traversal(self):
if self.left is not None:
self.left.in_order_traversal()
print(self.key, end=' ')
if self.right is not None:
self.right.in_order_traversal()
def insert_left(self, new_node):
self.left = new_node
def insert_right(self, new_node):
self.right = new_node
def search_val(self, key):
if self.key == key:
return self
if self.left is not None:
temp = self.left.search_val(key)
if temp is not None:
return temp
if self.right is not None:
temp = self.right.search_val(key)
return temp
return None
btree = None
print('Menu (this assumes no duplicate keys)')
print('insert <data> at root')
print('insert <data> left of <data>')
print('insert <data> right of <data>')
print('quit')
while True:
print('The inorder traversal of binary tree ', end='')
if btree is not None:
btree.in_order_traversal()
print()
do = input('What would you like to do? ').split()
operation = do[0].strip().lower()
if operation == 'insert':
data = int(do[1])
new_node = BinaryTree_structure(data)
sub_op = do[2].strip().lower()
if sub_op == 'at':
btree = new_node
else:
position = do[4].strip().lower()
key = int(position)
ref_node = None
if btree is not None:
ref_node = btree.search_val(key)
if ref_node is None:
print('No such key exists')
continue
if sub_op == 'left':
ref_node.insert_left(new_node)
elif sub_op == 'right':
ref_node.insert_right(new_node)
elif operation == 'quit':
break
输出
Menu (this assumes no duplicate keys) insert <data> at root insert <data> left of <data> insert <data> right of <data> quit The inorder traversal of binary tree What would you like to do? insert 45 at root The inorder traversal of binary tree 45 What would you like to do? insert 78 left of 45 The inorder traversal of binary tree 78 45 What would you like to do? insert 90 right of 45 The inorder traversal of binary tree 78 45 90 What would you like to do? quit
解释
创建了 ‘BinaryTree_structure’ 类。
它有一个 ‘set_root’ 函数，可帮助设置树的根值。
定义了一个名为 ‘in_order_traversal’ 的方法，可帮助以 ‘左->节点->右’ 的顺序遍历树。
定义了另一个名为 ‘insert_left’ 的方法，可帮助在根值的左侧添加一个元素。
定义了另一个名为 ‘insert_right’ 的方法，可帮助在根值的右侧添加一个元素。
另一个名为 ‘search_val’ 的方法被定义，它帮助从堆栈顶部删除一个值，并返回被删除的值。
给出了四个选项，例如‘插入到根’、‘插入到左侧’、‘插入到右侧’和‘退出’。
根据用户的输入/选择，执行相应的操作。
此输出显示在控制台上。
