树和二叉树

树和二叉树的定义

树的定义

树（Tree）是 \(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\) 。

满二叉树 深度为 \(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\) 。

二叉树的存储结构

顺序存储结构

----------------------------------------------------
| 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;
}

线索二叉树

线索二叉树的本质是方便进行前后结点的查询。

树和森林

树的存储结构

双亲表示法
孩子表示法
孩子兄弟表示法

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

这种存储结构的有点是它和二叉树的二叉链表表示完全一样，便于将一般的树结构转为二叉树进行处理，利用二叉树的算法来实现对树的操作。因此孩子兄弟表示法是应用较为普遍的一种树的存储表示法。

森林与二叉树的转换

森林转换为二叉树
二叉树转换为森林

树和森林的遍历

树的遍历（先根遍历、后根遍历）
森林的遍历（先序遍历、中序遍历）

哈夫曼树及其应用

哈夫曼树的基本概念

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

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

哈夫曼树的构造算法

哈夫曼编码

案例分析与实现

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