Python二叉树链式存储实现与代码示例

Python二叉树链式存储实现

本文介绍二叉树的链式存储结构，并提供Python代码示例，帮助你理解和掌握二叉树的基本操作。

1. 节点定义

首先，我们定义二叉树节点TreeNode，包含数据域data和指向左右子节点的指针left和right：

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

2. 创建二叉树

接下来，我们创建一个函数create_binary_tree，根据给定的列表构建二叉树：

def create_binary_tree(arr):
    if not arr:
        return None

    # 使用列表中的元素逐个创建树节点
    nodes = [TreeNode(data) if data is not None else None for data in arr]

    # 链接节点之间的关系
    for i in range(len(nodes)):
        if nodes[i] is None:
            continue

        left_index = 2 * i + 1
        right_index = 2 * i + 2

        if left_index < len(nodes):
            nodes[i].left = nodes[left_index]

        if right_index < len(nodes):
            nodes[i].right = nodes[right_index]

    return nodes[0]  # 返回根节点

该函数接受一个列表arr作为输入，根据列表元素创建树节点，并根据二叉树的性质连接节点关系，最终返回根节点。

3. 测试代码

以下代码演示如何使用create_binary_tree函数创建二叉树并访问节点值：

# 测试代码
arr = [1, 2, 3, 4, None, 5, 6]
root = create_binary_tree(arr)
print(root.data)         # 输出根节点的值
print(root.left.data)    # 输出左子节点的值
print(root.right.data)   # 输出右子节点的值

4. 总结

本文介绍了二叉树链式存储的基本概念，并使用Python实现了节点定义和二叉树创建过程。你可以根据这段代码进行扩展，实现更多二叉树操作，例如遍历、查找、插入和删除等。