使用链表实现二叉树的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