Python二叉树链式存储

二叉树的链式存储是指使用链表来存储二叉树。在链式存储中，每个节点都是一个对象，包含三个属性：data（存储节点的值）、left（左子树的引用）、right（右子树的引用）。其中，左子树和右子树也是二叉树。

下面是一个简单的示例代码，实现了二叉树的链式存储：

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self, root):
        self.root = TreeNode(root)

    def insert_left(self, node, value):
        if node.left is None:
            node.left = TreeNode(value)
        else:
            new_node = TreeNode(value)
            new_node.left = node.left
            node.left = new_node

    def insert_right(self, node, value):
        if node.right is None:
            node.right = TreeNode(value)
        else:
            new_node = TreeNode(value)
            new_node.right = node.right
            node.right = new_node

    def print_tree(self, traversal_type):
        if traversal_type == 'preorder':
            return self.preorder_print(self.root, '')
        elif traversal_type == 'inorder':
            return self.inorder_print(self.root, '')
        elif traversal_type == 'postorder':
            return self.postorder_print(self.root, '')
        else:
            print('Traversal type ' + str(traversal_type) + ' is not supported.')
            return False

    def preorder_print(self, start, traversal):
        if start:
            traversal += (str(start.data) + '-')
            traversal = self.preorder_print(start.left, traversal)
            traversal = self.preorder_print(start.right, traversal)
        return traversal

    def inorder_print(self, start, traversal):
        if start:
            traversal = self.inorder_print(start.left, traversal)
            traversal += (str(start.data) + '-')
            traversal = self.inorder_print(start.right, traversal)
        return traversal

    def postorder_print(self, start, traversal):
        if start:
            traversal = self.postorder_print(start.left, traversal)
            traversal = self.postorder_print(start.right, traversal)
            traversal += (str(start.data) + '-')
        return traversal

在上面的代码中，我们定义了两个类：`TreeNode`和`BinaryTree`。`TreeNode`表示一个二叉树的节点，包含节点的值`data`、左子树的引用`left`和右子树的引用`right`。`BinaryTree`表示整个二叉树，包含根节点`root`和一些方法，如插入节点、遍历等。

在构造函数`__init__`中，我们传入根节点的值，并以此创建根节点。在插入节点的方法中，我们首先判断当前节点的左子树或右子树是否为空，如果为空，直接插入新节点；否则，将当前节点的左子树或右子树作为新节点的左子树或右子树，再将新节点作为当前节点的左子树或右子树。

在遍历方法中，我们通过递归实现了前序遍历、中序遍历和后序遍历。这些方法都接受两个参数：当前节点和已遍历的节点字符串。在遍历时，我们先判断当前节点是否为空，如果不为空，就先遍历左子树，再遍历右子树，并将当前节点的值添加到已遍历的节点字符串中。最后，返回已遍历的节点字符串。

下面是一个示例代码，演示了如何使用上面的二叉树实现类：

# 创建二叉树
tree = BinaryTree('A')
tree.insert_left(tree.root, 'B')
tree.insert_right(tree.root, 'C')
tree.insert_left(tree.root.left, 'D')
tree.insert_right(tree.root.left, 'E')
tree.insert_left(tree.root.right, 'F')
tree.insert_right(tree.root.right, 'G')

# 前序遍历
print(tree.print_tree('preorder'))

# 中序遍历
print(tree.print_tree('inorder'))

# 后序遍历
print(tree.print_tree('postorder'))

输出结果：

A-B-D-E-C-F-G-
D-B-E-A-F-C-G-
D-E-B-F-G-C-A-

以上就是二叉树链式存储的Python实现。