树与二叉树

树（Tree）是一种非线性数据结构，用「节点 + 父子关系」描述层级结构，如文件系统目录、HTML 的 DOM、组织架构。二叉树是最简单也最常考的形态，是堆、二叉搜索树、平衡树、B+ 树的共同基础，面试题量占比很高。

树的术语

树由根节点向下分叉，常用术语：

• 根节点：没有父节点的顶层节点。
• 叶子节点：没有子节点的节点。
• 父节点 / 子节点 / 兄弟节点：直接相连的上下层节点、同一父节点的孩子。
• 度：一个节点拥有的子树个数；二叉树要求每个节点度 ≤ 2。
• 深度与高度：深度从根往下数，高度从叶子往上数。

          根 A
        /  |  \
       B   C   D        A 的度为 3，B、C、D 是 A 的孩子
          / \
         E   F          E、F 是叶子；整棵树的高度为 2

二叉树的特殊形态

二叉树每个节点最多两个子节点，分左子树与右子树，次序不可颠倒。两种常考的特殊形态：

• 满二叉树：除叶子外每个节点都有两个孩子，叶子全在最后一层。
• 完全二叉树：除最后一层外每层都满，最后一层节点从左到右连续——堆就是建在完全二叉树上的。

     满二叉树               完全二叉树
        1                      1
       / \                    / \
      2   3                  2   3
     / \ / \                / \
    4  5 6  7              4   5

二叉树的存储

• 顺序存储：用数组按下标存放。若节点下标为 i，则左孩子是 2i+1、右孩子是 2i+2、父节点是 (i-1)/2，适合完全二叉树。
• 链式存储：每个节点包含数据与左右孩子指针，通用性最强，实际最常用：

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None    # 左孩子
        self.right = None   # 右孩子

遍历：前序、中序、后序与层序

递归遍历按「根的位置」命名：前序（根左右）、中序（左根右）、后序（左右根）；层序用队列从上到下、从左到右逐层扫描。

def preorder(root):            # 前序遍历
    if root is None:
        return
    print(root.val, end=" ")   # 1. 访问根
    preorder(root.left)        # 2. 递归左子树
    preorder(root.right)       # 3. 递归右子树
# 对满二叉树 1(2(4,5),3(6,7)) 执行 preorder(root)：
# 输出：1 2 4 5 3 6 7

记忆点：中序 + 前序（或中序 + 后序）可以唯一重建一棵二叉树，是经典笔试题。

复杂度与面试要点

• 遍历 n 个节点，时间 O(n)；递归实现空间 O(h)，h 为树高，最坏退化为 O(n)。
• 完全二叉树用数组存储时，节点 i 的孩子下标是 2i+1 与 2i+2。
• 高频题：求最大深度、判断两棵树是否相同、层序遍历、镜像二叉树、验证二叉搜索树。
• 扩展方向：平衡二叉树、红黑树、B 树/B+ 树都是二叉树的进阶变体，先吃透二叉树再往上走。

小结：树用层级关系组织数据，二叉树因结构规整而成为算法题主流；熟记术语、两种特殊形态与四种遍历顺序，二叉树这关就算过了。