树与二叉树
树的概念
树（tree）是n（n>=0）个结点的有限集。在任意一棵非空树中：
- 有且仅有一个特定的结点称为（root）根结点
- 当n>1的时候，其余结点可以分为m（m>0）个互不相交的有限集：T₁、T₂、T₃…Tₘ。其中每一个有限集，又可以看成是一棵树，并且称之为根的子树。
图示：
- 根节点
- t₁
- t₂
- t₃
- t₄
树结点结构：
树结点包含一个数据元素以及若干个指向其子树的分支（指针）。
c
/* 示例代码 */
struct TreeNode
{
Element Data; // 数据域
struct TreeNode *t1, *t2, *t3...; // 多子树指针
};
struct node // 单链表结点
{
int index;
struct node *next;
};
// 树结点定义
struct TreeNode
{
int data;
struct node *childNode_ptr; // 分支结点的集合（链表形式存储子节点下标）
};创建树示例
c
// 创建一棵树（含10个结点）
struct tree t1[10];
// 初始化数据
t1[0].data = 1;
t1[1].data = 2;
t1[2].data = 3;
t1[3].data = 4;
t1[4].data = 5;
t1[5].data = 6;
t1[6].data = 7;
t1[7].data = 8;
t1[8].data = 9;
t1[9].data = 10;
// 建立关系：将根结点（t1[0]）的子节点下标存入链表
t1[0].childNode_ptr = /* 链表头指针，存储子节点下标 */;结点层次
- 定义：从根开始，根结点为第一层，根的子结点（孩子）为第二层，以此类推。
- 树的高度/深度：树中结点的最大层次。
结点的度
- 定义：结点拥有的子树数量。
- 叶子结点（终端结点）：度为0的结点。
- 分支结点：度不为0的结点。
二叉树
特点
- 每个结点最多有两个子树（不存在度>2的结点）。
- 子树分为左子树和右子树，次序不可颠倒。
二叉树的五大形态
- 空二叉树
- 只有一个根结点的二叉树
- 只有左子树的二叉树
- 只有右子树的二叉树
- 左右子树均存在的二叉树（完全二叉树）
二叉树的性质
第i层的最大结点数：至多 (2^{i-1}) 个结点（(i \geq 1)）。
- 第一层：(2^{0} = 1) 个结点
- 第二层：(2^{1} = 2) 个结点
- 第四层：(2^{3} = 8) 个结点
深度为k的二叉树最大结点数：至多 (2^{k} - 1) 个结点。
叶子结点与度为2结点的关系：
- 终端结点（叶子）数 (n_0)，度为2的结点数 (n_2)，满足 (n_0 = n_2 + 1)。
满二叉树：
- 深度为 (k) 且有 (2^{k} - 1) 个结点的二叉树（无法在不增加深度的情况下添加新结点）。
完全二叉树：
- 除最后一层外为满二叉树，最后一层结点从左至右连续排列。
- 对完全二叉树的结点按层次编号（从1到n），编号为 (i) 的结点：
- 左孩子（若存在）：编号 (2i)
- 右孩子（若存在）：编号 (2i + 1)
- 父结点：编号 (\lfloor i/2 \rfloor)（向下取整）
完全二叉树的深度：
- 具有 (n) 个结点的完全二叉树深度为 (\lfloor \log_2 n \rfloor + 1)（向下取整）。
- 示例：(n = 11)，深度为 (\lfloor \log_2 11 \rfloor + 1 = 4)。
二叉树的存储结构
顺序存储结构
- 使用数组存储，下标关系：
- 根结点：
tree[0] - 结点 (i) 的左孩子：
tree[2*i + 1] - 结点 (i) 的右孩子：
tree[2*i + 2]
- 根结点：
c
int tree[10] = {0};
tree[0] = 1; // 根结点
tree[1] = 2; // 根的左孩子（下标2*0+1）
tree[2] = 3; // 根的右孩子（下标2*0+2）链式存储结构
c
struct node
{
ElementType data;
struct node *lchild; // 左子节点指针
struct node *rchild; // 右子节点指针
};二叉树的遍历
访问：对结点进行打印、修改或对比操作，每个结点仅访问一次。
遍历方式
- 先序遍历：根 → 左子树 → 右子树（根左右）
- 中序遍历：左子树 → 根 → 右子树（左根右）
- 后序遍历：左子树 → 右子树 → 根（左右根）
- 层次遍历：按层从上到下、从左到右访问。
注意：遍历时需递归处理非终端结点的子树。
作业示例
给定先序和中序序列，求后序序列：
先序：
11 9 3 5 6 99 32 15
中序：3 5 6 9 11 15 32 99
后序：6 5 3 9 15 32 99 11中序：
1 2 3 6 9 15 33 52
先序：52 6 1 3 2 9 33 15
后序：2 3 1 15 33 9 6 52中序：
8 13 19 20 21 35 66
先序：35 21 13 8 19 20 66
后序：8 13 20 19 21 66 35
二叉排序树
定义
- 对任意结点：
- 左子树所有结点值 < 该结点值
- 右子树所有结点值 > 该结点值
- 注意：不存在值相等的结点。
结点插入
- 空树：新结点作为根结点。
- 非空树：
- 若新值 < 当前结点值：
- 左子树存在 → 递归比较左子树
- 左子树不存在 → 新结点作为左孩子
- 若新值 > 当前结点值：
- 右子树存在 → 递归比较右子树
- 右子树不存在 → 新结点作为右孩子
- 若新值 < 当前结点值：
示例插入序列：11 → 9 → 3 → 5 → 6 → 99 → 32 → 15
11为根9 < 11→ 成为11的左孩子3 < 11→ 递归至左子树9，3 < 9→ 成为9的左孩子
遍历特性
- 中序遍历：输出有序序列（从小到大）。
结点删除
- 叶子结点：直接删除，父结点指针置空。
- 只有左子树：
- 用左子树中最大结点替换被删结点。
- 若最大结点非左子树的根 → 调整其父结点指针指向其左孩子。
- 只有右子树：
- 用右子树中最小结点替换被删结点。
- 若最小结点非右子树的根 → 调整其父结点指针指向其右孩子。
- 左右子树均存在：
- 可选左子树最大结点或右子树最小结点替换。
平衡二叉树（AVL树）
定义
- 空树，或满足：
- 左右子树均为平衡二叉树
- 左右子树深度差绝对值 (\leq 1)
- 平衡因子：结点左子树深度 (-) 右子树深度（取值范围：(-1, 0, 1)）。
平衡操作
左深左插（LL型）：
- 场景：左子树的左侧新增结点导致失衡。
- 操作：单向右旋（以失衡结点的左孩子为轴右旋）。
失衡结点（6） 旋转后： / 5 5（IB_left） / \ / 4 6 4
右深右插（RR型）：
- 场景：右子树的右侧新增结点导致失衡。
- 操作：单向左旋（以失衡结点的右孩子为轴左旋）。
失衡结点（6） 旋转后： \ 7 7（IB_right） / \ \ 6 8 8
左深右插（LR型）：
- 场景：左子树的右侧新增结点导致失衡。
- 操作：
- 先对左子树左旋（转为LL型）
- 再整体右旋
右深左插（RL型）：
- 场景：右子树的左侧新增结点导致失衡。
- 操作：
- 先对右子树右旋（转为RR型）
- 再整体左旋
作业：
- 绘制右深右插（RR型）平衡操作示意图。
- 实现RR型平衡代码。
哈夫曼树（最优二叉树）
应用背景
- 电报通信中字符的二进制编码优化：高频字符短编码，低频字符长编码。
- 哈夫曼编码：以字符频率为权值，构建哈夫曼树，路径左分支标0、右分支标1。
定义
- 带权路径长度（WPL）：树中所有叶子结点的（路径长度 × 权值）之和。
- 最优二叉树：WPL最小的二叉树。
构建步骤
- 构建森林：
- 将 (n) 个权值 ({w_1, w_2, \dots, w_n}) 看作 (n) 棵仅含根结点的树，存入优先队列（按权值升序）。
- 创建新树：
- 从队列取出权值最小的两棵树 (A, B)。
- 创建新结点 (P)，权值 (w_P = w_A + w_B)，(A, B) 分别为 (P) 的左右子树。
- 加入新树：
- 将 (P) 加入优先队列。
- 重复合并：
- 重复步骤2-3，直至队列只剩一棵树 → 此树为哈夫曼树。
优先队列实现
- 使用有序链表维护结点权值升序排列。
- 支持操作：插入（自动排序）、删除最小元素。
作业：
- 完成未遍历的二叉树后序和层次遍历结果。
- 实现二叉排序树的销毁和循环删除结点操作。
- 每日完成20道数据结构相关题目（截图提交至学习群）。