Chapter 1 Binary Tree

理论基础

二叉树是一种非线性数据结构，由节点组成，每个节点最多有两个子节点，通常称为"左子节点"和"右子节点"。

基本概念

  1. 节点（Node）：二叉树的基本单位，包含数据和指向子节点的引用
  2. 根节点（Root）：二叉树的顶部节点，没有父节点
  3. 叶节点（Leaf）：没有子节点的节点
  4. 父节点（Parent）：有子节点的节点
  5. 子节点（Child）：某节点下一层的节点
  6. 兄弟节点（Sibling）：共享同一父节点的节点
  7. 节点的度（Degree）：节点的子节点数量
  8. 树的高度/深度：从根节点到最远叶节点的最长路径上的节点数
  9. 节点的层级（Level）：从根节点到该节点的边的数量加1

二叉树的类型

  1. 满二叉树（Full Binary Tree）：每个节点要么有0个子节点，要么有2个子节点
  2. 完全二叉树（Complete Binary Tree）：除了最后一层外，其他层都被完全填充，且最后一层的所有节点都尽可能靠左排列
  3. 完美二叉树（Perfect Binary Tree）：所有内部节点都有两个子节点，所有叶节点都在同一层
  4. 平衡二叉树（Balanced Binary Tree）：任意节点的左右子树高度差不超过1
  5. 二叉搜索树（Binary Search Tree）：左子树上所有节点的值都小于根节点的值，右子树上所有节点的值都大于根节点的值

二叉树的性质

  1. 第i层的最大节点数为 $2^(i-1)$
  2. 深度为k的二叉树最多有 $2^k - 1$ 个节点
  3. 任何非空二叉树，若叶节点数为n0，度为2的节点数为n2，则 n0 = n2 + 1
  4. 具有n个节点的完全二叉树的高度为 ⌊log₂n⌋ + 1

二叉树的存储结构

  1. 链式存储：每个节点包含数据域和指向左右子节点的指针
  2. 顺序存储：使用数组存储，对于索引为i的节点，其左子节点索引为2i+1，右子节点索引为2i+2

二叉树的遍历方式

  1. 深度优先遍历（DFS）
  • 前序遍历（Preorder）：根 → 左 → 右
  • 中序遍历（Inorder）：左 → 根 → 右
  • 后序遍历（Postorder）：左 → 右 → 根
  1. 广度优先遍历（BFS）
  • 层序遍历（Level Order）：按层从左到右遍历所有节点

二叉树的定义

Go

type TreeNode struct {
    Val any
    Left *TreeNode
    Right *TreeNode
}