树和二叉树

树和二叉树的定义

树的定义

树是 \(n（n \ge 0）\) 个结点的有限集，它或为空树（\(n = 0\)）；或为非空树，对于非空树\(T\)：

有且仅有一个称之为根的结点。
除根结点以外的其余结点可分为\(m（m \ge 0）\)个互不相交的有限集\(T_{1}， T_{2}， ...，T_{m}\)，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

视频课

树的定义

树的基本术语

结点：树中的一个独立单元。
结点的度：结点拥有的子树数称为结点的度。
树的度：树的度是树内各结点度的最大值。（比较所有结点的度，找出最大值。不是累加）
叶子：度为0的结点称为叶子或终端结点。
非终端结点：度不为0的结点称为非终端结点或分支结点。
双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。
兄弟：同一个双亲的孩子之间互称兄弟。
祖先：从根到该结点所经分支上的所有结点。
子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。
层次：结点的层次从根开始定义起，根为第一层，根的孩子为第二层。
堂兄弟：双亲在同一层的结点互为堂兄弟。
树的深度：树中结点的最大层次称为树的深度或高度。（最多能数多少层）
有序树和无序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），即称该树为有序树，否则称为无序树。
森林：是\(m ( m \ge 0 )\)棵互不相交的树的集合。（一棵树可以看成特殊的森林；给森林的各子树加一个双亲结点，森林就变成树；树一定是森林，森林不一定是树。）

视频课

树的基本术语

二叉树的定义

二叉树（Binary Tree）是\(n（n \ge 0）\) 个结点所构成的集合，它或为空树（\(n = 0\)）；或为非空树，对于非空树\(T\)：

有且仅有一个称之为根的结点；
除根结点以外的其余结点分为两个互补相交的子集\(T_{1}\)和\(T_{2}\)，分别称为\(T\)的左子树和右子树，且\(T_{1}\)和\(T_{2}\)本身又都是二叉树。

二叉树

二叉树与树一样具有递归性质，二叉树与树的区别主要有以下两点：

二叉树每个结点至多只有两颗子树（即二叉树中不存在度大于2的结点）；
二叉树的子树有左右之分，其次序不能任意颠倒。

视频课

树和二叉树的抽象数据类型定义

视频课

抽象数据类型定义

二叉树的性质和存储结构

二叉树的性质

二叉树具有下列重要特性：

性质1 在二叉树的第 \(i\) 层上至多有 \(2^{i-1}\) 个结点（ \(i \ge 1\) ）（某一层）

性质2 深度为 \(k\) 的二叉树至多有 \(2^{k}-1\) 个结点（ \(k \ge 1\) ）（整棵树）

性质3 对任何一棵二叉树 \(T\) ，如果其终端结点数为 \(n_{0}\) ，度为2的结点数为 \(n_{2}\) ，则 \(n_{0}=n_{2}+1\) 。

视频课

二叉树性质1、2、3

满二叉树 深度为 \(k\) 且含有 \(2^{k}-1\) 个结点的二叉树。

满二叉树的特点是：第一层上的结点数都是最大结点数，即每一层 \(i\) 的结点数都具有最大值 \(2^{i-1}\) 。

满二叉树

完全二叉树 深度为 \(k\) 的，有 \(n\) 个结点的二叉树，当且仅当其每一个结点都与深度 \(k\) 的满二叉树中编号从 \(1\) 至 \(n\) 的结点一一对应时，称之为完全二叉树。

完全二叉树的特点是：

叶子结点只可能在层次最大的两层上出现；
对任一结点，若其右分支下的子孙的最大层次为 \(l\) ，则其左分支下的子孙的最大层次必为 \(l\) 或 \(l+1\) 。

完全二叉树

视频课

满二叉树和完全二叉树

完全二叉树在很多场合下出现，下面的性质4和性质5是完全二叉树的两个重要特性。

性质4 具有 \(n\) 个结点的完全二叉树的深度为 \(\left \lfloor log_{2}n \right \rfloor + 1\) 。

性质5 如果对一棵有 \(n\) 个结点的完全二叉树（其深度为 \(\left \lfloor log_{2}n \right \rfloor + 1\) ）的结点按层序编号（从第 \(1\) 层到第 \(\left \lfloor log_{2}n \right \rfloor + 1\) 层，每层从左到右），则对任一结点 \(i（1 \le i \le n）\) ，有

如果 \(i = 1\) ，则结点 \(i\) 是二叉树的根，无双亲；如果 \(i > 1\) ，则其双亲 \(PARENT(i)\) 是结点 \(\left \lfloor i / 2 \right \rfloor\) 。
如果 \(2i > n\) ，则结点 \(i\) 无左孩子（结点 \(i\) 为叶子结点）；否则其左孩子 \(LCHILD(i)\) 是结点 \(2i\) 。
如果 \(2i+1 > n\) ，则结点 \(i\) 无右孩子；否则其右孩子 \(RCHILD(i)\) 是结点 \(2i+1\) 。

视频课

二叉树性质4、5

二叉树的存储结构

顺序存储结构

----------------------------------------------------
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
----------------------------------------------------
完全二叉树

-------------------------------------------------
| 1 | 2 | 3 | 4 | 5 | 0 | 0 | 0 | 0 | 0 | 6 | 7 |
-------------------------------------------------
一般二叉树（0表示不存在此结点）
对于一般二叉树，更适合采用链式存储结构

链式存储结构

二叉链表。每个结点有三个成员：数据域、左孩子指针域、右孩子指针域。

视频课

遍历二叉树和线索二叉树

遍历二叉树

若规定先左后右，则有：

DLR - 先（根）序遍历

void PreOrderTraversal(binary *tree)
{
    if (tree == NULL) return;

    printf("%d", tree->data);
    PreOrderTraversal(tree->left);
    PreOrderTraversal(tree->right);
    return;
}

LDR - 中（根）序遍历

void InOrderTraversal(binary *tree)
{
    if (tree == NULL) return;

    InOrderTraversal(tree->left);
    printf("%d", tree->data);
    InOrderTraversal(tree->right);
    return;
}

LRD - 后（根）序遍历

void PostOrderTraversal(binary *tree)
{
    if (tree == NULL) return;

    PostOrderTraversal(tree->left);
    PostOrderTraversal(tree->right);
    printf("%d", tree->data);
    return;
}

二叉树遍历

遍历分析

从根结点出发，逆时针围绕树一周，每个节点都会访问三次。
- 第1次经过访问 = 先序遍历
- 第2次经过访问 = 中序遍历
- 第3次经过访问 = 后序遍历
根据遍历序确定二叉树
- 若二叉树中各结点值均不相同，则二叉树的先序、中序和后序都是唯一的。
- 由先序和中序可以确定唯一的二叉树。
- 由中序和后序可以确定唯一的二叉树。
非递归遍历可以手动维护一个显示栈。
层次遍历利用队列。将孩子入队，再将孩子的孩子入队。
建立二叉树、复制、求结点数、求叶子结点数等直观的解法就是递归，后续可以在递归基础上优化。
用二叉树表示算术表达式
- 先序（前缀表示，波兰式）
- 中序（中缀表示）
- 后续（后缀表示，逆波兰式）
- 示例：
  - 前缀表达式 -*a+bcd
  - 中缀表达式 a*(b+c)-d
  - 后缀表达式 abc+*d-
- 转换：
  - 一个运算符，两个操作数，如：A + B 或 +AB 或 AB+
  - 中缀转前缀。添加括号，从左向右，遇到左括号将运算符左移至当前这层括号的左侧。最后删除多余括号。
  - 中缀转后缀。添加括号，从右向左，遇到右括号将运算符右移至当前这层括号的右侧。最后删除多余括号。
  - 前缀转中缀。从右向左找运算符和操作数（一个运算符和两个操作数），添加括号后，符号移到操作数中间。
  - 后缀转中缀。从左向右找运算符和操作数（一个运算符和两个操作数），添加括号后，符号移到操作数中间。
- 计算：
  - 前缀表达式：从右向左，遇到操作数入栈，遇到操作符时两个操作数出栈计算，计算结果重新入栈。
  - 后缀表达式：从左向右，遇到操作数入栈，遇到操作符时两个操作数出栈计算，计算结果重新入栈。

视频课

线索二叉树

线索二叉树

利用二叉链表的空指针域。
得到一个二叉树的遍历序列（前序、中序和后序）。
将空的左孩子指针域指向遍历序列的前驱。
将空的右孩子指针域指向遍历序列的后继。

对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线序化。

视频课

线索二叉树

树和森林

树的存储结构

双亲表示法

定义结构数组（结构体数组），存放树的结点。每个结点包含两个域：数据域（存放结点本身信息）和父结点域（指示本结点的父结点在数组中的位置）。
```
 数据域
     父结点域
  -------
0 |R |-1|
1 |A | 0|
2 |B | 0|
3 |C | 1|
4 |D | 2|
  -------
```
孩子表示法
1. 将树的所有的结点存储为一个线性表。线性表以单链表为存储结构。
2. 如果结点有n个孩子，则该结点为链表头结点，后面跟随n个结点。
3. 如果结点没有孩子，则该结点表示空链表。
孩子兄弟表示法

又称二叉树表示法，或二叉链表表示法，即以二叉链表做树的存储结构。

类似于二叉链表，一个结点有三个成员：数据域，自己的第一个孩子指针域，自己的下一个兄弟指针域。

视频课

森林与二叉树的转换

森林转换为二叉树
- 树转二叉树：兄弟相连留长子。
- 二叉树转树：左孩右右连双亲，去掉原来右孩线。（就是树转二叉树的逆运算）。
- 森林转二叉树：树变二叉树根相连，以第一颗树根结点为二叉树的根。
二叉树转换为森林

去掉全部右孩线，孤立二叉再还原。

视频课

树和森林的遍历

树的遍历（先根遍历、后根遍历、按层次遍历）
森林的遍历
- 先序遍历：依次对每一棵树进行先根遍历
- 中序遍历：依次对每一棵树进行后根遍历

视频课

树和森林的遍历

哈夫曼树及其应用

哈夫曼树的基本概念

哈夫曼（Huffman）树又称为最优树，是一类带权路径长度最短的树。

路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。
路径长度：路径上的分支数目称作路径长度。
树的路径长度：从树根到每一结点的路径长度之和。
权：赋予某个实体的一个量，是对实体的某个或某些属性的数值化描述。实体有结点（元素）和边（关系）两大类，所以对应有结点权和边权。
结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。
树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作 \(WPL = \sum_{k=1}^{n}w_{k}l_{k}\) 。
哈夫曼树：假设有m个权值 \({w_{1}, w_{2}, ..., w_{m}}\) ，可以构造一棵含n个叶子结点的二叉树，每个叶子结点的权为 \(w_{i}\) ，则其中带权路径长度 \(WPL\) 最小的二叉树称做最优二叉树或哈夫曼树。
- 满二叉树不一定是哈夫曼树。
- 哈夫曼树中权越大的叶子离根越近。
- 具有相同带权结点的哈夫曼树不唯一。

哈夫曼树的构造算法

哈夫曼树的合并是树与树之间的合并。选择较小的两棵树（依据根结点的权值）进行合并。

哈夫曼树的结点的度数为0或2，没有度为1的结点。
包含n个叶子结点的哈夫曼树共有2n - 1个结点。
包含n棵树的森林要经过n-1次合并才能形成哈夫曼树，共产生n-1个新结点。

构造哈夫曼树

哈夫曼编码

例如通信中，按如下编码

A - 00
B - 01
C - 10
D - 11

ABACCDA
00010010101100

若将编码设计为长度不等的二进制编码即让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换的二进制字符串遍可以减少。

A - 0
B - 00
C - 1
D - 01

ABACCDA
000011010

当时前面的 0000在翻译时就会出现重码
0000
AAAA ABA BB

统计字符集中每个字符在报文中出现的概率（概率越大要求编码越短）。
利用哈夫曼树的特点：权越大的叶子离根越近；将每个字符的概率值作为权值，构造哈夫曼树。则概率越大的结点，路径越短。
在哈夫曼树的每个分支上标0或1：结点的左分支标0，右分支标1。把从根到每个叶子的路径上的标号连接起来，作为该叶子代表的字符的编码。

哈夫曼编码

性质1：哈夫曼编码是前缀码。
性质2：哈夫曼编码是最优前缀码。

案例分析与实现

利用二叉树求解表达式的值
表达式树的创建

视频课