数据结构与算法 / 系统课时

二叉树的存储方式

二叉树的存储方式

二叉树既可以用节点引用保存,也可以映射到数组下标。本课用同一棵树比较两种表示方法,掌握父子下标公式、空位处理和适用场景,避免在稀疏树中误用顺序存储。

学习目标

  • 掌握二叉树链式节点的基本结构
  • 正确使用数组中的父子下标公式
  • 根据树的形状选择合适的存储方式

两种存储思路

二叉树中每个节点最多有两个子节点,分别占据左、右位置。链式存储让每个节点保存值、左子节点引用和右子节点引用,可以自然表示任意形状;顺序存储把节点放入数组,通过下标计算父子关系。根节点下标为 0 时,下标为 ii 的节点满足:

left=2i+1,right=2i+2,parent=⌊i−12⌋\text{left}=2i+1,\quad \text{right}=2i+2,\quad \text{parent}=\left\lfloor\frac{i-1}{2}\right\rfloor

父节点公式只适用于 i>0i>0,因为根节点没有父节点。

二叉树链式存储与顺序存储对比

什么时候选择哪一种

完全二叉树除最后一层外都填满,最后一层节点从左到右连续,因此数组中的位置通常很紧凑。二叉堆正是利用这一特点,用数组获得连续内存和常数时间的父子定位。

普通二叉搜索树的形状可能很稀疏。若某个较深节点只有右孩子,数组必须保留沿途空位,否则下标关系会被破坏。此时链式存储通常只为实际节点分配空间,更合适。

主示例:用两种方式表示同一棵树

下面的树中,节点 C 没有左孩子但有右孩子 F。数组必须在下标 5 处保留 None,才能让 F 位于正确的右孩子位置。

python
class BinaryNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def children_of(items, index):
    if index < 0 or index >= len(items) or items[index] is None:
        return None, None

    left_index = 2 * index + 1
    right_index = 2 * index + 2

    # 越过数组边界或落在空位时,都表示没有对应孩子
    left = items[left_index] if left_index < len(items) else None
    right = items[right_index] if right_index < len(items) else None
    return left, right

root = BinaryNode(
    "A",
    BinaryNode("B", BinaryNode("D"), BinaryNode("E")),
    BinaryNode("C", None, BinaryNode("F")),
)

array_tree = ["A", "B", "C", "D", "E", None, "F"]

print("链式根节点:", root.value)
print("链式左孩子:", root.left.value)
print("数组中 B 的孩子:", children_of(array_tree, 1))
print("数组中 C 的孩子:", children_of(array_tree, 2))

预期输出

text
链式根节点: A
链式左孩子: B
数组中 B 的孩子: ('D', 'E')
数组中 C 的孩子: (None, 'F')

边界与复杂度

链式存储访问某个已知节点的左右孩子是 O(1)O(1),但查找目标节点仍可能需要遍历。数组存储同样能在 O(1)O(1) 时间计算父子位置,不过空间消耗取决于最大下标;极端稀疏树可能出现大量空位。

数组末尾没有后代的连续空位可以省略,但中间用于维持下标关系的空位不能删除。左、右位置通常具有语义,也不能为了紧凑而任意交换。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

二叉树的存储方式

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通