树与二叉树

概述

树是一种层次结构的数据模型，节点之间存在父子关系；二叉树是每个节点最多有两个子节点的树。

基本术语

• 结点：树中的基本元素。
• 度：结点拥有的子树数量。
• 叶子结点：度为 0 的结点。
• 深度/高度：从根到某结点的层数（或从结点到叶子的层数）。

二叉树的性质

• 第 $i$ 层最多有 $2^{i-1}$ 个结点。
• 高度为 $h$ 的二叉树，结点总数最多为 $2^{h}-1$。
• 对于完全二叉树，可用数组顺序存储并快速定位父子结点。

遍历方式

• 前序遍历：根 → 左 → 右。
• 中序遍历：左 → 根 → 右。
• 后序遍历：左 → 右 → 根。
• 层序遍历：按层从上到下，从左到右。

典型应用

• 表达式树与语法分析。
• 堆与优先队列。
• 二叉搜索树与平衡树。