使用链表实现二叉树的Python程序

当使用链表实现二叉树数据结构时，定义一个设置根节点、一个执行中序遍历的方法、一个插入元素到根节点左侧的方法、一个插入元素到根节点右侧的方法以及一个搜索值的方法。

下面是同样的演示——

更多Python相关文章，请阅读：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):
            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('菜单（假定没有重复键）')
print('在根节点插入 <data>')
print('在 <data> 左侧插入 <data>')
print('在 <data> 右侧插入 <data>')
print('退出')

while True:
    print('二叉树的中序遍历 ', end='')
    if btree is not None:
        btree.in_order_traversal()
    print()

    do = input('您想做什么？').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('没有这样的键')
                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

输出

菜单（假定没有重复键）
在根节点插入 <data>
在 <data> 左侧插入 <data>
在 <data> 右侧插入 <data>
退出
二叉树的中序遍历
您想做什么？ insert 45 at root
二叉树的中序遍历 45
您想做什么？ insert 78 left of 45
二叉树的中序遍历 78 45
您想做什么？ insert 90 right of 45
二叉树的中序遍历 78 45 90
您想做什么？ quit

解释

• 创建了‘BinaryTree_structure’类。

• 它有一个‘set_root’函数，帮助设置树的根值。

• 定义了一个名为‘in_order_traversal’的方法，帮助按照‘Left->Node->Right’的顺序遍历树。

• 另一个名为‘insert_left’的方法被定义，帮助在根值左侧添加一个元素。

• 另一个名为‘insert_right’的方法被定义，帮助在根值右侧添加一个元素。

• 另一个名为‘search_val’的方法被定义，帮助从栈顶删除一个值，并返回删除的值。

• 提供了四个选项，例如‘插入到根’、‘插入到左侧’、‘插入到右侧’和‘退出’。

• 根据用户的输入/选择，执行相应的操作。

• 在控制台上显示该输出。