知识总结

满二叉树

每一层都达到最大节点数的二叉树。

• 深度为h的满二叉树有 2^h - 1 个节点
• 第i层有 2^(i-1) 个节点

完全二叉树

除最后一层外，每层都是满的，且最后一层节点靠左排列。

性质（编号从1开始）：

• 节点i的左子节点：2i
• 节点i的右子节点：2i + 1
• 节点i的父节点：i / 2（下取整）
• n个节点的完全二叉树高度：⌊log₂n⌋ + 1

二叉搜索树（BST）

• 左子树所有节点的值 < 根节点的值
• 右子树所有节点的值 > 根节点的值
• 中序遍历得到的是有序序列

平衡二叉树（AVL树）

• 任意节点的左右子树高度差不超过1
• 查找、插入、删除的时间复杂度均为 O(log n)

堆

• 最大堆（大根堆）：父节点 ≥ 子节点
• 最小堆（小根堆）：父节点 ≤ 子节点
• 堆是完全二叉树
• 用于实现优先队列

二叉树的节点数关系

设度为0的节点（叶子）有 n₀ 个，度为2的节点有 n₂ 个：

$$n0 = n2 + 1$$