树与二叉树

树是 $n$（$n \geq 0$）个结点的有限集合：
- 当 $n = 0$ 时，称为空树。
- 非空树满足：
  - 有且仅有一个根结点。
  - 其余结点分为 $m$（$m \geq 0$）个互不相交的子树，每个子树本身也是一棵树。

结点与关系：
- 根结点：没有父结点的结点。
- 叶子结点（终端结点）：没有子结点的结点。
- 分支结点（非终端结点）：至少有一个子结点的结点。
- 父结点（双亲结点）与子结点（孩子结点）：直接相连的上下层结点。
- 兄弟结点：具有相同父结点的结点。
- 堂兄弟结点：父结点不同但处于同一层的结点。
- 祖先结点与子孙结点：从根到某结点的路径上的所有前驱结点称为祖先，所有后继结点称为子孙。
路径与属性：
- 路径：从根到某结点的唯一通路。
- 路径长度：路径中边的数量。
- 层次（深度）：根结点为第 1 层，向下逐层递增。
- 结点的高度：从该结点到最远叶子结点的路径长度。
- 树的高度/深度：树中结点的最大层次数。
度与类型：
- 结点的度：结点拥有的子结点数。
- 树的度：树中所有结点度的最大值。
- 有序树：子树顺序不可交换的树（如二叉树）。
- 无序树：子树顺序可交换的树。
- 森林：由 $m$（$m \geq 0$）棵互不相交的树组成的集合。

度为 $m$ 的树 vs. $m$ 叉树：

层与结点数关系：
- 度为 $m$ 的树：第 $i$ 层最多有 $m^{i-1}$ 个结点。
- $m$ 叉树：第 $i$ 层最多有 $m^{i-1}$ 个结点。
高度与结点数极值：
- 高度为 $h$ 的 $m$ 叉树：
  - 最多结点数：$\frac{m^h - 1}{m - 1}$（满 $m$ 叉树，等比数列求和公式）。
  - 最少结点数：$h$（每层仅 1 个结点）。
- 高度为 $h$、度为 $m$ 的树：至少 $h + m - 1$ 个结点。
最小高度公式：
- 含 $n$ 个结点的 $m$ 叉树的最小高度：
  $h_{\text{min}} = \lceil \log_m \left( n(m - 1) + 1 \right) \rceil$
- 推导：前 $h-1$ 层最多有 $\frac{m^{h-1} - 1}{m - 1}$ 个结点，需满足 $n \leq \frac{m^h - 1}{m - 1}$。

结点数与度数关系：$\text{结点总数} = \sum (\text{所有结点的度}) + 1$。
树的度与层结点数：度为 $m$ 的树第 $i$ 层最多有 $m^{i-1}$ 个结点。
高度与结点数极值：
- 最大结点数：利用等比数列求和公式 $\frac{m^h - 1}{m - 1}$。
- 最小结点数：每层仅 1 个结点，总数为 $h$。
最小高度公式：通过完全填满时的层数推导，使用对数函数计算。

二叉树是 $n(n \geq 0)$ 个结点的有限集合：
- 空二叉树：当 $n=0$ 时。
- 非空二叉树：
  - 由一个根结点和两个互不相交的左子树、右子树组成。
  - 左子树和右子树分别也是二叉树。
- 特点：
  - 每个结点最多有两棵子树（左子树和右子树）。
  - 左右子树严格有序，不可颠倒（有序树）。

满二叉树：
- 定义：高度为 $h$ 且含有 $2^h -1$ 个结点的二叉树。
- 特点：
  - 只有最后一层有叶子结点。
  - 不存在度为1的结点。
  - 按层序从1开始编号，结点$i$的左孩子为$2i$，右孩子为$2i+1$，父结点为$\lfloor i/2 \rfloor$。
完全二叉树：
- 定义：当且仅当其每个结点都与高度为 $h$ 的满二叉树中编号为 $1 \sim n$ 的结点一一对应。
- 特点：
  - 最后两层可能有叶子结点。
  - 最多只有一个度为1的结点。
  - 分支结点编号满足 $i \leq \lfloor n/2 \rfloor$，叶子结点编号满足 $i > \lfloor n/2 \rfloor$。
二叉排序树（BST）：
- 定义：
  - 空树或满足：左子树所有结点关键字 < 根结点关键字 < 右子树所有结点关键字。
  - 左右子树也是二叉排序树。
平衡二叉树（AVL树）：
- 定义：任一结点的左子树和右子树深度之差不超过1。

结点数与度数关系：
- 设度为0、1、2的结点数分别为 $n_0, n_1, n_2$，则：
  $
  n_0 = n_2 + 1
  $
- 推导：总结点数 $n = n_0 + n_1 + n_2$，总边数 $n -1 = n_1 + 2n_2$，联立得 $n_0 = n_2 +1$。
层结点数上限：
- 第 $i$ 层最多有 $2^{i-1}$ 个结点（二叉树）。
- 第 $i$ 层最多有 $m^{i-1}$ 个结点（$m$ 叉树）。
高度与结点数极值：
- 高度为 $h$ 的二叉树最多有 $2^h -1$ 个结点（满二叉树）。
- 高度为 $h$ 的 $m$ 叉树最多有 $\frac{m^h -1}{m -1}$ 个结点。
完全二叉树高度公式：
- 结点数为 $n$ 的完全二叉树最小高度：
  $
  h = \lceil \log_2 (n+1) \rceil \quad \text{或} \quad h = \lfloor \log_2 n \rfloor +1
  $

结点数奇偶性分析：
- 若完全二叉树有 $2k$ 个结点（偶数）：
  - $n_1 =1$, $n_0 =k$, $n_2 =k-1$。
- 若完全二叉树有 $2k-1$ 个结点（奇数）：
  - $n_1 =0$, $n_0 =k$, $n_2 =k-1$。
关键操作判断：
- 判断结点 $i$ 是否有左孩子：$2i \leq n$。
- 判断结点 $i$ 是否有右孩子：$2i+1 \leq n$。
- 判断结点 $i$ 是否为叶子结点：$i > \lfloor n/2 \rfloor$。

顺序存储：
- 适用场景：完全二叉树。
- 数组索引规则：根结点从1开始，结点 $i$ 的左孩子为 $2i$，右孩子为 $2i+1$，父结点为 $\lfloor i/2 \rfloor$。
- 缺点：非完全二叉树存储时存在空间浪费。

链式存储：

二叉链表：

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

三叉链表（含父结点指针）：

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild, *parent;
} BiTNode, *BiTree;

题型1：计算叶子结点数
步骤：
- 利用 $n_0 = n_2 +1$ 结合总结点数联立求解。
- 示例：已知 $n_1=5$, $n_2=3$，则 $n_0=4$，总结点数 $n=5+3+4=12$。
题型2：完全二叉树高度计算
公式选择：
- 当题目强调“最小高度”时使用 $\lceil \log_2 (n+1) \rceil$。
- 当题目给出结点数范围时使用 $\lfloor \log_2 n \rfloor +1$。
题型3：判断完全二叉树合法性
关键点：
- 检查结点编号是否连续填充，无中间空缺。
- 验证最后一个结点的父结点是否存在。
题目1：已知完全二叉树有1000个结点，求叶子结点数。
解析：
- 根据完全二叉树性质，当 $n=1000$（偶数）时，$n_1=1$，$n_0=500$，$n_2=499$。
- 答案：500个叶子结点。
题目2：高度为5的满二叉树，求第3层结点数。
解析：
- 第3层最多有 $2^{3-1}=4$ 个结点。
- 答案：4个结点。
题目3：判断结点数n=15的完全二叉树高度。
解析：
- 使用公式 $h = \lceil \log_2 (15+1) \rceil = \lceil 4 \rceil =4$。
- 答案：高度为4。

数据结构 > 学习笔记

#树

树与二叉树

http://kjuan.xyz/2025/04/13/树与二叉树/

Author

k卷

Posted on

April 13, 2025

Licensed under