数据结构：二叉树

二叉树（Binary Tree） 是一种常见的数据结构，它由若干节点组成，每个节点最多只有 两个子节点：

• 左子节点（Left Child）
• 右子节点（Right Child）

因此称为 二叉树

每个节点通常包含三个部分：

Node {
    value
    left
    right
}

简单结构示例：

        A
       / \
      B   C
     / \   \
    D   E   F

其中：

• A 是 根节点（Root）
• B、C 是 A 的 子节点
• D、E 是 B 的 子节点

满二叉树（Full Binary Tree）

如果一棵树的 所有节点要么有两个子节点，要么没有子节点，则称为满二叉树。

        A
       / \
      B   C
     / \ / \
    D  E F  G

特点：

• 每个节点要么 0 个子节点
• 要么 2 个子节点

完全二叉树（Complete Binary Tree）

完全二叉树要求：

• 除最后一层外，其余层全部填满
• 最后一层节点从 左往右连续排列

示例：

        1
       / \
      2   3
     / \  /
    4  5 6

这种结构非常适合 数组存储，因此 堆（Heap） 就是完全二叉树。

二叉搜索树（BST）

二叉搜索树（Binary Search Tree）满足：

左子树 < 根节点 < 右子树

示例：

        8
       / \
      3   10
     / \    \
    1   6    14

特点：

• 查询效率高
• 平均时间复杂度：O(log n)

但如果树退化成链表：

1
 \
  2
   \
    3

时间复杂度会退化为：

O(n)

总结

二叉树是最基础也是最重要的数据结构之一，其核心特点是

• 每个节点最多 两个子节点
• 支持 高效搜索
• 可以扩展为多种高级数据结构

常见变种包括：

• 二叉搜索树（BST）
• AVL 树
• 红黑树
• 堆（Heap）

理解二叉树是学习 算法与数据结构 的重要基础。