使用链表实现二叉树的Python程序
当需要使用链表实现二叉树数据结构时，设置根节点的方法，进行中序遍历的方法，在根节点的左边插入元素，插入元素的方法根节点的右侧，并定义了搜索值的方法。
以下是相同的演示-
示例
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):
ifself.leftis not None:
self.left.in_order_traversal()
print(self.key, end=' ')
ifself.rightis 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):
ifself.key== key:
return self
ifself.leftis not None:
temp = self.left.search_val(key)
if temp is not None:
return temp
ifself.rightis not None:
temp = self.right.search_val(key)
return temp
return None
btree = None
print('Menu (this assumes no duplicate keys)')
print('insert at root')
print('insert left of ')
print('insert right of ')
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 at root insert left of insert right of 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”的方法，它帮助从堆栈顶部删除一个值，并返回删除的值。
给出了四个选项，例如“插入根目录”、“插入左侧”、“插入右侧”和“退出”。
根据用户的输入/选择，执行相应的操作。
此输出显示在控制台上。