本章重点
树和二叉树的定义
树和二叉树的抽象数据类型定义
二叉树的性质和存储结构
- 二叉树的五个性质
  - 满二叉树
  - 完全二叉树
- 二叉树的存储结构
  - 二叉树的顺序存储
  - 二叉树的链式存储
    - 三叉链表
遍历二叉树和线索二叉树
树和森林
哈夫曼树及其应用

本章重点

树和二叉树 - 图2

树和二叉树的定义

树的定义

树是n(n>=0)个结点的有限集。

若n = 0，称为空树。
若n > 0，则它满足以下两个条件：
- 有且只有一个特定的称为根(Root)的结点
- 其余结点可以分为m(m>=0)个互不相交的有限集T1,T2,T3, …Tm，其中每一个集合本身又是一棵树，并称为根的子树。

树的表示方式：

树的基本术语

结点：数据元素以及指向子树的分支
根结点：非空树中无前驱结点的结点。
结点的度：结点拥有的子树数。
树的度：树内各结点的度的最大值。
度为0的结点称为叶结点或者终端结点，度不为0的结点称为非终端结点或者分支结点，根结点以外的分支结点称为内部结点。
结点的子树的根称为该结点的孩子，该结点称为孩子的双亲。
我们通常把根结点称为树的第一层，根结点的孩子称为树的第二层，同理，孩子的孩子就是第三层 … 依次类推。我们把同一层的结点称为堂兄弟。
结点的祖先：从根到该结点所经分支上的所有结点。
结点的子孙：以某结点为根的子树中的任一结点。
树的深度：树中结点的最大层次。
有序树：树中结点的各子树从左至右有次序(最左边为第一个孩子)
无序树：树中结点的各子树无次序。
森林：是m(m>=0)棵互不相交的树的集合。
把根结点删除树就变成了森林，一棵树可以看成是一个特殊的森林，给森林的各子树加上双亲结点，森林就变成了树，即：树一定是森林，但森林不一定是树。

线性结构	特点	树结构	特点
第一个数据元素	无前驱	根结点	无双亲
最后一个数据元素	无后继	叶子结点	无孩子
其他数据元素	一个前驱，一个后继	其他结点	一个双亲，多个孩子
一对一		一对多

二叉树的定义

二叉树是n(n>=0)个结点的有限集，它或者是空集(n = 0)，或者由一个根节点及两颗互不相交的分别称作这个根的左子树和右子树的二叉树组成
特点

每个结点最多有两个孩子(二叉树中不存在度大于2的结点)
子树有左右之分，其次序不能颠倒
二叉树可以是空集合，根可以有空的左子树和空的右子树

二叉树和普通树的区别
二叉树不是树的特殊情况，它们是两个概念

二叉树必须要区分左右子树，即使只有一颗子树也要区分。
树只有一个孩子时，无需区分左右次序

二叉树的结构简单、规律性强。
所有树都能转换为唯一对应的二叉树，不失一般性。
普通树(多叉树)若不转化为二叉树，则运算很难实现
二叉树在树结构中起着非常重要的作用，因为二叉树的算法操作简单，而且任何树都可以和二叉树互相转换。这样就解决了树的存储结构及其运算中存在的复杂性。

案例引入

利用二叉树求解表达式的值
以二叉树表示表达式的递归定义如下：

若表达式为数或为简单变量，则相应二叉树中仅有一个根结点，其数据域存放该表达式信息。
若表达式为 “第一操作数运算符第二操作数” 的形式，则相应的二叉树以左子树表示第一操作数，右子树表示第二操作数，根结点的数据域存放运算符(若为一元运算符，则左子树为空)，其中，操作数本身又为表达式。

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

二叉树的性质和存储结构

二叉树的五个性质

性质一：在二叉树的第 i 层上至多有 2i-1 个结点(i>=1)

性质二：深度为k的二叉树至多有个 2k-1 结点(k>=1)

性质三：对任何一颗二叉树T，如果其终端结点(度为0)的个数为n**0，度为2的结点数为n2，则n0=n2**+1。

满二叉树

一颗深度为k且2k-1个结点的二叉树称为满二叉树。
特点：

每一层上的结点数都是最大结点数(即每层都满)
叶子结点全在最底层
满二叉树

对满二叉树结点位置进行编号

编号规则：从根结点开始，自上而下，自左而右。
每一结点位置都有元素
满二叉树在同样深度的二叉树中结点个数最多
满二叉树在同样深度的二叉树中叶子结点个数最多

如下图：
满二叉树.png

完全二叉树

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

满二叉树一定是完全二叉树，所以在满二叉树中，从最后一个结点开始，连续去掉任意个结点，还是一颗完全二叉树(一定是连续的去掉)，但是完全二叉树不一定是满二叉树。

特点：

叶子只能分布在层次最大的两层上。
对任一结点，如果其右子树的最大层次为i，则其左子树的最大层次必为i或i+1

性质四：具有n个结点的完全二叉树的深度为。

完全二叉树之前已经提到，它是一颗具有n个结点的二叉树，且每个结点按照层序编号。所以它的结点数一定小于等于满二叉树的结点数 2k-1 。但一定比满二叉树的上一层结点多，即一定多于2k-1-1。
所以可以推导出：2k-1-1< n <= 2k-1 (n为结点数)
由于结点n是整数，n <= 2k-1 意味着 n < 2k， 2k-1-1< n 意味着 2k-1 <= n。
所以可以得到：2k-1 <= n < 2k
不等式两边取对数，得到：k-1 <= log2n < k ，而k作为深度也是整数，因此。
性质4表明了完全二叉树结点数n于完全二叉树深度k之间的关系。

性质五：如果对一棵有n个结点的完全二叉树(其深度为)的结点按层序编号(从第一层搭配第层，每层从左到右)，对任一结点j(1<=i<=n)有：

如果i=1，则结点是二叉树的根，无双亲；如果i>1，其双亲结点是 [i/2] //向下取整。
如果2i > n则结点无左孩子(结点i为叶子结点)，否则其左孩子是2i。
如果2i+1 > n，则结点i无右孩子，否则其右孩是结点2i+1。

性质5表明了完全二叉树中双亲结点编号与孩子结点编号之间的关系。

总结：

求树的第 i 层有多少个结点：2**i-1**。
求一棵树至多能有几个结点：2**k**-1。
求一棵树有多少个叶子结点：n**0=n2**+1。
求一棵完全二叉树的深度：。
求一棵完全二叉树某结点的双亲结点：i / 2 ; 某结点的左孩子：i * 2 ；求某结点的右孩子：i * 2 + 1。
二叉树的存储结构
二叉树的顺序存储
实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素。

那么如果二叉树中有空闲的结点怎么办呢，我们可以如下方法表示，当结点没有数据时，就置为0。

二叉树的顺序存储表示

typedef int TElemType;    /* 树结点的数据类型 */
typedef TElemType SqBiTree[MAXTSIZE]; 
SqBiTree bt;

二叉树顺序存储的缺点
首先是大小固定，一个数组的大小是定长的，如果数中的元素变化特别大，这时候就不合适了。
并且还存在空间浪费的情况，最坏情况下：深度为k的且只有k个结点的单支树需要度为2k-1的一维数组
特点：

结点间关系蕴含在其存储位置中
浪费空间，适合存储满二叉树和完全二叉树

二叉树的链式存储

二叉树的链式存储表示

typedef struct BiNode {
    TElemType data;
    struct BiNode *lchild, *rchild;
} BiNode, *BiTree;

存储方式

特点：在n个结点的二叉链表中，有 n+1 个空指针域。
分析：有n个结点，每个结点两个指针域，所以n个结点必有2n个指针域(链域)。除根结点外，每个结点必有一个双亲，所以每个结点必有一个链域指向它，可以推导出只会有 n-1 个结点的链域存放指针，指向非空子女结点。
所以 空指针数目 = 2n - (n - 1) = n+1。

三叉链表

二叉链表中有两个指针域，分别指向左右孩子，但是在三叉链表中，我们可以再创建一个指针域来存放结点的双亲。
三叉链表的表示形式

typedef struct TriTNode {
    TElemType data;
    struct TriTNode *lchild, *parent, *rchild;
} TriTNode, *TriTree;

遍历二叉树和线索二叉树

遍历二叉树

遍历定义：顺着某一条搜索路径巡防二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次(又称周游)。
遍历目的：得到树中所有结点的一个线性排列。
遍历用途：它是树结构插入、删除、修改、查找和排序算法的前提，是二叉树一切运算的基础和核心

遍历方法
二叉树是由根结点、左子树和右子树组成的，那么我们只需要依次遍历二叉树的三个组成部分，便是遍历了整个二叉树。

遍历二叉树算法描述

若规定先左后右，则只有前三种情况：
DLR —— 先(根)序遍历
LDR —— 中(根)序遍历
LRD —— 后(根)序遍历

先序遍历二叉树	中序遍历二叉树	后序遍历二叉树
若二叉树为空，则空操作。否则： 1. 访问根结点 1. 先序遍历左子树 1. 先序遍历右子树	若二叉树为空，则空操作。否则： 1. 中序遍历左子树 1. 访问根结点 1. 中序遍历右子树	若二叉树为空，则空操作。否则： 1. 后序遍历左子树 1. 后序遍历右子树 1. 访问根结点

遍历二叉树的操作定义

先序遍历二叉树的操作定义：
对于只有三个结点的二叉树，那么先序遍历的顺序就是ABC

那么当二叉树的结点多时，仍然遵循这个顺序，所以得到下图的结果：

解析：
A为根，依据顺序则下一个是B，B继续依照前序遍历的顺序，所以下一个是E，然后E的下一个左子树是空，所以跳过去访问右子树，所以下一个是L，至此ABEL遍历完成。
然后回退到E，E的左右子树已经访问完成，再次回退到B，B的右子树为空，继续回退到A，然后开始访问A的右子树D，依据刚刚同样的方法，可以得出接下来的顺序为DHMLJ。

中序遍历二叉树的操作定义：
对于只有三个结点的二叉树，那么先序遍历的顺序就是BAC

那么当二叉树的结点多时，仍然遵循这个顺序，所以得到下图的结果：

解析：
A为根，依据中序遍历原则，先访问左子树B，然后B再访问左子树E，E中没有左子树，所以不操作，回退到E，访问E的内容，然后访问右子树L。右子树L访问完就回退到B，访问B的内容，然后B的右子树为空，不执行操作，再回退到A，访问A的内容，至此ELBA。
然后访问A的右子树D，再访问D的左子树H，继续访问左子树M，访问M的内容，然后回退到H，访问H的内容，依据之前同样的方法，可以得出接下来的顺序为MHIDJ。

后序遍历二叉树的操作定义：
对于只有三个结点的二叉树，那么先序遍历的顺序就是BCA

那么当二叉树的结点多时，仍然遵循这个顺序，所以得到下图的结果：

解析：
A为根，依据后续遍历规则访问左子树B，再访问B的左子树E，E的左子树为空，不执行操作，然后访问E的右子树L，访问L的内容，然后再回退到E，访问L的内容，E的兄弟结点(B的右子树)为空，不执行操作，所以回退到B，访问B的内容。至此LEB。
然后找到B的兄弟结点D，D的左子树为H，H的左子树为M，访问M的内容，然后找到M的兄弟结点I，访问I的内容，依据之前同样的方法，可以得出接下来的顺序为MIHJDA

例题一：

遍历结果：
先：ABDGCEHF
中：DGBAEHCF
后：GDBHEFCA

例题二：

遍历结果：
先：-+ab-cd/ef（表达式的前缀表示 -> 波兰式）
中：a+bc-d-e/f（表达式的中缀表示）
后：abcd-*+ef/-（表达式的后缀表示 -> 逆波兰式）

根据遍历序列确定二叉树

若二叉树中各结点的值均不相同，则二叉树结点的先序序列、中序序列和后序序列都是唯一的。
由二叉树的先序序列和中序序列，或由二叉树的后序序列和中序序列都可以唯一确定一颗二叉树。
例题一：
已知二叉树的先序和中序序列，构造出相应的二叉树

分析：由先序序列确定根，由中序序列确定左右子树

由先序知根为A，则由中序知左子树为CDBFE，右子树为IHGJ。

然后再分别从左右子树的序列中找到新的根，左右子树。

依次类推，直到得到二叉树

例题二：

遍历算法的实现

遍历算法递归实现

先序遍历算法

Status PreOrderTraverse(BiTree T) {
    // 如果结点为空就返回(结束递归的条件)
    if (T == NULL) return OK;
    else {
        // 访问根结点(也可以包装到一个函数中)
        printf("%d\n", T->data);
        // 递归访问左子树
        PreOrderTraverse(T->lchild);
        // 递归访问右子树
        PreOrderTraverse(T->rchild);
    }
}

先序遍历算法思想图解

二叉树的中序遍历算法

Status InOrderTraverse(BiTree T) {
    // 如果结点为空就返回(结束递归的条件)
    if (T == NULL) return OK;
    else {
        // 递归访问左子树
        InOrderTraverse(T->lchild);
        // 访问根结点
        printf("%d\n", T->data);
        // 递归访问右子树
        InOrderTraverse(T->rchild);
    }
}

二叉树的后序遍历算法

Status PostOrderTraverse(BiTree T) {
    // 如果结点为空就返回(结束递归的条件)
    if (T == NULL) return OK;
    else {
        // 递归遍历右子树
        PostOrderTraverse(T->lchild);
        // 递归遍历左子树
        PostOrderTraverse(T->rchild);
        // 访问根
        printf("%d\n", T->data);
    }
}

遍历算法分析

可以发现这三种遍历方式的代码十分相似，如果去掉输出语句，从递归的角度看，三种算法是完全相同的，或说这三种算法的访问路径是相同的，只是访问结点的时机不同。
如图

从虚线的出发点到终点的路径上，每个结点经过3次。
第一次经过时访问 = 先序遍历
第二次经过时访问 = 中序遍历
第三次经过时访问 = 后序遍历

时间复杂度：O(n) // 每个结点只访问一次
空间复杂度：O(n) // 每访问一个结点就要创建一个新栈
注意：前面是说每个结点都会经过三次，并不是每个结点都访问三次，只不过是在每一次经过的时候访问的时机不同。所以时间复杂度是O(n)，而不是O(3n)。

遍历算法非递归实现

以中序遍历算法为例：
二叉树中序遍历的非递归算法的关键：在中序遍历过某结点的整个左子树后，如何找到该结点的根以及右子树。
基本思想：

建议一个栈
根结点进栈，遍历左子树
根结点出栈，输出根结点，遍历右子树

代码：

Status InOrderTraverse_stack(BiTree T) {
    SqStack S;
    BiTree p;
    BiTree q = (BiTree)malloc(sizeof(BiNode));
    InitStack(&S);
    p = T;
    // 循环条件：树还有元素存在 或者 栈S不为空
    while (p || !StackEmpty(&S)) {
        if (p) {
            // 只要p存在就将p压栈
            Push(&S, *p);
            // p 指向左孩子结点
            p = p->lchild;
        }
        else { // 能到这里说明 p 已经指向最左边的孩子还左孩子结点了(NULL)
            // 将栈顶元素重新赋值给p
            Pop(&S, q);
            // 此时的栈顶元素就是一段二叉树中的根，输入结点内容
            printf("%c", q->data);
            // 左孩子已经访问完毕，开始访问右孩子
            p = q->rchild;
            // p为某个根结点的右孩子后，还是需要依据左根右的原则
            // 所以到上面继续对左孩子压栈
        }
    }
    free(q);
    return OK;
}

二叉树的层次遍历

对于一棵二叉树，从根结点开始，按从上到下、从左到右的顺序访问每一个结点。每个结点仅访问一次。
如图的这么一棵二叉树的遍历结果：

算法设计思路：

将根结点入队
队不为空是循环：从队列中出列一个结点*p，并访问它
1. 若它有左孩子，将左孩子进队；
2. 若它有右孩子，将右孩子经对；

代码：

Status LevelOrder(BiTree b) {
    BiTree p = (BiTree)malloc(sizeof(BiNode));
    SqQueue qu;
    InitQueue(&qu);    // 初始化队列
    EnQueue(&qu, *b);    // 根节点入队
    // 循环条件：队列中还有元素
    while (!QueueEmpty(&qu)) {
        // 出队一个元素赋值给p
        DeQueue(&qu, p);
        // 输出p的值
        printf("%c ", p->data);
        // 将p结点的左右孩子入队
        if (p->lchild) EnQueue(&qu, *(p->lchild));
        if (p->rchild) EnQueue(&qu, *(p->rchild));
    }
    free(p);
    return OK;
}

二叉树的建立

按先序遍历序列建立二叉树的二叉链表

从键盘输入二叉树的结点信息，建立二叉树的存储结构。
在建立二叉树的过程中按照二叉树先序方式建立。

但是按照先序遍历的方法建立出的二叉树可能都是：ABCDEGF

所以我们为了建立出一棵唯一的树，我们可以创建一些空结点，我们可以用空格或者 “#” 来表示空结点

左边这棵树可以表示为ABC##DE#G##F###
右边这棵树可以表示为ABC##DEG##F####

代码：

Status CreateBiTree(BiTree* T) {
    char ch;
    scanf("%c", &ch);
    if (ch == '#')
        (*T) = NULL;  // 如果为#代表该结点为空
    else {
        // 不是空结点就为结点开辟空间
        if (!((*T) = (BiTree)malloc(sizeof(BiNode)))) exit(OVERFLOW);
        // 为结点的的data域赋值
        (*T)->data = ch;
        // 递归生成左右子节点
        CreateBiTree(&((*T)->lchild));
        CreateBiTree(&((*T)->rchild));
    }
    return OK;
}

二叉树的其他操作

复制二叉树
如果是空树，递归结束。否则，申请新结点空间，复制根结点内容(递归复制左右子树)。
代码：

Status TreeCopy(BiTree T, BiTree* NewT) {
    // 如果T的根结点为空，新的结点也赋值为空
    if (T == NULL) {
        (*NewT) = NULL;
        return 0;
    }
    else {
        // 创建新的空间，并将T的值赋值给新树NewT
        (*NewT) = (BiTree)malloc(sizeof(BiNode));
        (*NewT)->data = T->data;
        // 递归遍历二叉树
        TreeCopy(T->lchild, &(*NewT)->lchild);
        TreeCopy(T->rchild, &(*NewT)->rchild);
    }
}

计算二叉树的深度
如果是空树，则深度为0。否则，递归计算左子树的深度记为m，递归计算右子树的深度记为n，二叉树的深度则为m于n的较大值加1。
代码：

int getDepth(BiTree T) {
    // 如果是空树直接返回0
    if (T == NULL) return 0;
    // 获取左右子树的的深度
    int m = getDepth(T->lchild);
    int n = getDepth(T->rchild);
    // 返回当前m和n的较大值+1
    return m > n ? m + 1 : n + 1;
}

计算二叉树结点总数
如果是空树，则结点为0。否则，结点个数为左子树的结点格式 + 右子树的结点个数 + 1。
代码：

int NodeCount(BiTree T) {
    if (T == NULL) return 0; 
    return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}

计算叶子结点的个数
如果是空树，则叶子结点个数为0。否则，为左子树的叶子结点个数 + 右子树叶子结点个数
代码：

int LeafCount(BiTree T) {
    if (T == NULL) return 0;
    if (T->lchild == NULL && T->rchild == NULL) {
        return 1;
    }
    return LeafCount(T->lchild) + LeafCount(T->rchild);
}

线索二叉树

当我们使用二叉链表存储结构时，可以很方便的找出某个结点的左右孩子。但是一般情况下，无法直接找到该结点的某种遍历序列中的前驱和后继结点。
解决这个问题有多种方法：

通过遍历寻找 —— 费时间
再增加两个指针域，分别指向其前驱结点和后继结点 —— 增加了存储负担
利用二叉链表中的空指针域 —— 推荐

同时之前的二叉树还有一个弊端，对于一个有n个结点的二叉链表，每个结点有指向左右孩子的两个指针域，所有n个结点一共有2n个指针域。而n个结点的二叉树一共有n-1条分支线，也就是说，其实存在 2n-(n-1) = n+1个空指针域。

利用二叉链表中的空指针域：
如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱，如果某个结点的右孩子为空，则将空的右孩子域改为指向其后继。
这种改变指向的指针成为”线索”。加上了线索的二叉树称为线索二叉树，对二叉树按某种遍历次序使其变为线索二叉树的过程叫做线索化。

为区分lchild和rchild指针到底时指向孩子的指针，还是指向前驱或者后继的指针，对二叉链表中每个结点增设两个标志域ltag和rtag，并约定：

ltag = 0 —— lchild 指向该结点的左孩子
ltag = 1 —— rchild 指向该结点的前驱
rtag = 0 —— rchild 指向该结点的右孩子
rtag = 1 —— rchild 指向该结点的后继、

这样，结点的表示为

typedef struct BiThrNode {
    TElemType data;
    int ltag, rtag;
    struct BiThrNode* lchild, * rchild;
}BiThrNode, * BiThrTree;

以下这么一棵二叉树，即使采用了线索二叉树，可是还有两个位置悬空，我们应该怎么解决这种问题呢？

为了避免这种悬空问题，我们可以增设一个头结点：

ltag = 0，lchild指向根结点
rtag = 1，rchild指向遍历序列中最后一个结点
遍历序列中第一个结点的 lchild 域和最后一个结点的 rchild 域都指向右结点

树和森林

树：是n(n>=0)个结点的有限集。若n = 0，称为空树。
森林：是m(m>=0)棵互不相交的树的集合。

树的存储结构

双亲表示法

实现：定义结构数组，存放树的结点，每个结点含两个域。
数据域：存放结点本身信息
双亲域：指示本结点的双亲结点在数组中的位置。
如下图中的数组，就可以表示右图中的这棵树

除此之外，在存储树的结构体中，我们还需要定义两个变量，用于表示根在数组中的位置和总共结点的个数。
双亲表示法定义代码：

#define MAX_TREE_SIZE 100
typedef struct {
    TElemType data;    // 存放树结点的数据
    int parent;        // 双亲位置域
} PTNode;
typedef struct {
    PTNode nodes[MAX_TREE_SIZE];    // 存放整棵树的数组
    int r, n;                        // 根结点的位置和结点个数
} PTree;

特点：找双亲容易，找孩子难。

孩子表示法

把每个结点的孩子结点排列起来，看成是一个线性表，用单链表存储。则n个结点右n个孩子链表(叶子的孩子链表为空表)。而n个头指针又组成一个线性表，用顺序表(含n个元素的结构数组)存储。
如下图中的数组 + 链表，就可以表示右图中的这棵树

孩子表示法定义代码：

// 孩子结点
typedef struct CTNode {
    int child;                // 孩子的在数组中的索引
    struct CTNode* next;    // 下一个孩子结点
} *ChildPtr;
// 根结点
typedef struct {
    TElemType data;            // 存放结点的数据
    ChildPtr firstNode;        // 第一个孩子结点
} CTBox;
// 结点数组
typedef struct {
    CTBox nodes[MAX_TREE_SIZE];    // 存放整棵树的数组
    int r, n;                    // 根结点的位置和结点个数
} CTree;

特点：找孩子容易，找双亲难。
由于这个特点，所以我们延申出了一种带双亲的孩子链表，这样即弥补了孩子表示法的不足，也弥补了双亲表示法的不足。唯独不好的是，增加了很多存储空间。

孩子兄弟表示法

实现：用二叉链表作为树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。如左图中的二叉链表就可以表示右图这棵树：

孩子兄弟表示法定义代码：

typedef struct CSNode {
    TElemType data;        // 存放结点的数据
    struct CSNode* firstChild, * nextSibling;    // 两个指针分别指向第一个孩子和兄弟
}CSNode, * CSTree;

特点：找孩子和兄弟容易，双双亲难，但是可以将一棵普通树转换成熟悉的二叉树。
我们也可以根据需要在增加一个域，来存储树的双亲结点，这样就可以让操作更加便捷，但是同样增加了存储空间。

树和二叉树的转换

由于树的操作是比较复杂的，所以我们通常是把树转换成二叉树进行操作，利用二叉树的算法来实现对树的操作。
由于树和二叉树都可以用二叉链表作存储结构，则以二叉链表作媒介可以到处树和二叉树之间的一个对应关系。
我们使用孩子兄弟表示法：

由上图可以得到转换的步骤是：

加线：在兄弟之间加一条线
抹线：对每个结点，除了其左孩子外，去除其余其余孩子之间的关系。
旋转：以树的根结点为轴心，将整棵树顺时针旋转45°。

树变二叉树口诀：兄弟相连留长子

那么同理，我们由一棵二叉树也可以转换为树，步骤是：

加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子….沿分支找到所有右孩子，都与p的双亲用线连起来。
抹线：抹掉原二叉树中双亲与右孩子之间的连线。
调整：将结点按层次排列，形成树结构。

二叉树变树口诀：左孩右右连双亲，去掉原来右孩线

森林与二叉树的转换

森林转换成二叉树步骤：

将各棵树分别转换成二叉树
将每棵树的根节点用线相连
以第一棵树的根结点为二叉树的根，再以根结点为轴心，顺时针旋转。构造二叉树树型结构。

森林变二叉树口诀：树变二叉根相连

二叉树转换成森林步骤：

抹线：将二叉树中根节点与其右孩子连线，其沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树。
还原：将孤立的二叉树还原成树

二叉树变森林口诀：去掉全部右孩线，孤立二叉再还原

树和森林的遍历

树的遍历

树的遍历方式和二叉树基本一致，树是没有中序遍历的

先序遍历
后序遍历
层次遍历

森林的遍历

将森林看作由三部分构成

森林中第一棵树的根结点
森林中第一棵树的子树森林
森林中其他树构成的森林

先序遍历
若森林不空，则

访问森林中第一颗树的根结点
先序遍历森林中第一棵树的子树森林
先序遍历森林中(除第一棵树外)其余树构成的森林

即：依次从左至右对森林中的每一棵树进行先根遍历。

后序遍历
若森林不空，则

后序遍历森林中第一棵树的子树森林
访问森林中第一棵树的根结点
后序遍历森林中(除第一棵树外)其余树构成的森林

即：依次从左至右对森林中的每一棵树进行后根遍历

哈夫曼树及其应用

引入

编程：将学生的百分制成绩转换为五分制成绩

代码非常的简单，可以是要if语句实现，或者switch语句实现(以下使用if语句)：

char grade;
int score = 60;
if (score >= 0 && score < 60)
    grade = 'E';
else if (score < 70)
    grade = 'D';
else if (score < 80)
    grade = 'C';
else if (score < 90)
    grade = 'B';
else if (score <= 100)
    grade = 'A';
else
    grade = 0;

以上每个情况下都有两个分支，就可以看成是一个判断树。
判断树：用于描述分类过程的二叉树

假设成绩的分布情况如上，且数据量很大，则需要考虑程序的操作时间，若学生的成绩数据供10000个，则：

而同样的程序如果我们进行树化，则可以大大减少程序的运行次数

所以问题就是能不能找到一种效率最高的判别树呢？这就需要哈夫曼树(最优二叉树)

哈夫曼树的基本概念

路径：从树中一个结点到另一个结点之间的分支构成两个结点间的路径。
结点的路径长度：两结点间路径上的分支树。
树的路径长度：从树根到每一个结点的路径长度之和，记作：TL

可以发现：结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树，但是路径长度最短的二叉树却不一定是完全二叉树

权：将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。
结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度：树中所有叶子结点的带权路径长度之和。
记作：树和二叉树 - 图65

可以看出，我们用相同的叶子结点，相同的权值，构造不同的二叉树，那么树的带权路径长度是不同的。
哈夫曼树：最优树，即带权路径长度(WPL)最短的树
注意：带权路径长度最短是在度相同的树中比较而得的结果，因此有最优二叉树、最优三叉树之称等等。

这四棵二叉树进行比较，路径最短的那两棵树，就是哈夫曼树。
所有可以发现：

满二叉树不一定是哈夫曼树
哈夫曼树中权越大的叶子离根越近
具有相同带权结点的哈夫曼树不唯一

哈夫曼树的构造算法

由上面得到哈夫曼树中权越大的叶子离根越进，所有我们只要先把权最小的结点先构造，后面再构造权值大的树，这种算法就被称为贪心算法。

哈夫曼算法(构造哈夫曼树的方法)

哈夫曼算法口诀：

构造森林全是根
选用两小造新树
删除两小添新人
重复2、3剩单根

依据上面的例子可以得到规律：

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

总结：

哈夫曼树构造算法的实现

采用顺序存储结构 —— 一维结构数组
结点类型定义：

typedef struct {
    int weight;                // 权重
    int parent, lch, rch;    // 双亲，左孩子，右孩子
} HTNode, *HuffmanTree;

前面已经得出，哈夫曼树中共有2n-1个结点，所以我们可以创建数组时，不使用0作为下标，创建一个2
n大小的数组即可。
我们用上面树的指针创建一个数组：HuffmanTree H;，当我们需要修改第i个结点的权值为5，即可表示为H[i].weight=5;。

举例：有n = 8，权值为W={ 7,19,2,6,32,3,21,10}，构造哈夫曼树，可以得到如下的结果

所以可以得到哈夫曼树的实现规则：

初始化HT[1…2n-1]：lch = rch = parent = 0;
输入初始n个叶子结点：置HT[1…n]的weight值。
进行以下n-1次合并，依次产生n-1个结点HT[i]，i=n+1…2n-1。
- 在HT[1…i-1]中选两个未被选过(从parent == 0的结点中选)的weight最小的两个结点HT[s1]和HT[s2]，s1和s2为两个最小的结点下标。
- 修改HT[s1]和HT[s2]的parent值：HT[s1].parent = HT[s2].parent=i;
- 修改新产生的HT[i]：
  - HT[i].weight = HT[s1].weight + HT[s2].weight;
  - HT[i].lch = s1, HT[i].rch = s2;

构造算法实现：

void CreateHuffmanTree(HuffmanTree* HT, int n) {
    int m, i, s1, s2;
    if (n <= 1) return;
    m = 2 * n - 1;
    *HT = (HuffmanTree)malloc(sizeof(HTNode) * (m + 1));
    if (*HT == NULL)
        exit(OVERFLOW);
    HuffmanTree p = *HT;
    // 将所有数据域初始化为0
    for (i = 1; i <= m; i++) {
        (p + i)->parent = 0;
        (p + i)->lch = 0;
        (p + i)->rch = 0;
    }    
    // 初始化前n个结点的数据
    for (i = 1; i <= n; i++) {
        scanf("%d", &(p + i)->weight);
    }
    // 初始化完成，下面开始建立哈夫曼树
    for (i = n + 1; i <= m; i++) {
        //getSmall(HT, &s1, &s2, i - 1);
        Select(*HT, i - 1, &s1, &s2);
        (p + s1)->parent = (p + s2)->parent = i;
        (p + i)->weight = (p + s1)->weight + (p + s2)->weight;
        (p + i)->lch = s1;
        (p + i)->rch = s2;
    }
}

查找算法实现：

//HT数组中存放的哈夫曼树，end表示HT数组中存放结点的最终位置，s1和s2传递的是HT数组中权重值最小的两个结点在数组中的位置
void Select(HuffmanTree HT, int end, int* s1, int* s2)
{
    int min1, min2;
    //遍历数组初始下标为 1
    int i = 1;
    //找到还没构建树的结点
    while (HT[i].parent != 0 && i <= end) {
        i++;
    }
    min1 = HT[i].weight;
    *s1 = i;
    i++;
    while (HT[i].parent != 0 && i <= end) {
        i++;
    }
    //对找到的两个结点比较大小，min2为大的，min1为小的
    if (HT[i].weight < min1) {
        min2 = min1;
        *s2 = *s1;
        min1 = HT[i].weight;
        *s1 = i;
    }
    else {
        min2 = HT[i].weight;
        *s2 = i;
    }
    //两个结点和后续的所有未构建成树的结点做比较
    for (int j = i + 1; j <= end; j++)
    {
        //如果有父结点，直接跳过，进行下一个
        if (HT[j].parent != 0) {
            continue;
        }
        //如果比最小的还小，将min2=min1，min1赋值新的结点的下标
        if (HT[j].weight < min1) {
            min2 = min1;
            min1 = HT[j].weight;
            *s2 = *s1;
            *s1 = j;
        }
        //如果介于两者之间，min2赋值为新的结点的位置下标
        else if (HT[j].weight >= min1 && HT[j].weight < min2) {
            min2 = HT[j].weight;
            *s2 = j;
        }
    }
}

哈夫曼编码

在远程通讯中，要将待传字符转换成由二进制的字符串：

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

可以发现，即使我们使用了上面的规则减短了编码长度，但是还是有重码的问题出现。
所以关键就是：要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀。这种编码就称作前缀编码。

什么样的前缀码能够使得电文总长最短 —— 哈夫曼编码：

统计字符串中每个字符在电文中出现的平均概率(概率越大，要求编码越短)。
利用哈夫曼树的特点：权越大的叶子离根越近。将每个字符的概率值作为权值，构造哈夫曼树。则概率越大的结点，路径越短。
在哈夫曼树的每个分支上标上0或1：

把结点的左分支标0，右分支标1
把从根到每个叶子的路径上的标号连接起来，作为该叶子代表的字符的编码。

在哈夫曼编码中，一定找不到重复的编码。

由上面两个问题可以得到哈夫曼编码的两个性质：

性质一：哈夫曼编码是前缀码
性质二：哈夫曼编码是最优前缀码

哈夫曼编码的算法实现

那么这样一棵哈夫曼树怎么获取到对应的哈夫曼编码呢？
首先我们从叶子结点开始查找，查找它的双亲结点，然后判断该叶子是其双亲的左孩子or右孩子，如果是左孩子则它的最后一位编码为0，反之为1。
然后利用同样的方法找到双亲的双亲，然后判断双亲是双亲的双亲的左孩子or右孩子，左孩子则倒数第二位编码为0，反之为1。以同种方法遍历，直到遇到根，根的双亲结点位置为0(空)，则结束循环。
但是这样的获取到的编码和我们的需求肯定是相反的，所以我们可以提前准备一个数组cd，数组的最后一位为’\0’，然后从叶子开始每读取到一个编码，就从后向前存储一位。
最后把cd数组的内容正序读取到特定的编码表中，当循环结束，编码表中即存储着我们需要的编码。

实现代码：

void CreateHuffmanCode(HuffmanTree HT, char** HC[], int n) {
    int i, c, f, start;
    // 创建编码表
    (*HC) = (char**)malloc(sizeof(char*) * (n + 1));
    // 临时存放编码的动态数组空间
    char cd[255] = { 0 };
    cd[n - 1] = '\0';   // 编码结束符
    // 逐个字符求哈夫曼编码
    for (i = 1; i <= n; i++) {
        start = n - 1;
        c = i;
        f = HT[i].parent;
        // 从叶子结点向上回溯，知道根结点(根结点的的parent==0)
        while (f != 0) {
            --start;
            cd[start] = (HT[f].lch == c) ? '0' : '1';
            c = f;
            f = HT[f].parent;
        }
        // 为第i个字符串编码分配空间
        (*HC)[i] = (char*)malloc(sizeof(char) * (n - start));
        // 将指定位置处的临时空间cd复制到HC的当前行中
        strcpy((*HC)[i], &cd[start]);
    }
}

哈夫曼编码应用举例 —— 文件编码与解码

如下面的一段明文，如果采用ASCII编码存储，则存储空间如图：

这就是由于ASCII编码采用的是等长编码形式，如果我们采用哈夫曼编码形式，则可以大幅度减少大小，预计只需要1596bit，和原来相比空间减少了将近50%。这就是哈夫曼编码的优势。

利用哈夫曼编码进行文件的编码和解码
编码：

输入各字符及其权值(先统计文档中字符的权值)
构造哈夫曼树 —— HT[i]
进行哈夫曼编码 —— HC[i]
查HC[i]，得到各个字符的哈夫曼编码

解码：

构造哈夫曼树
依次读入二进制码
读入0，则走向左孩子；读入1，则走向右孩子。
一旦到达某叶子时，即可译出字符
然后再从根触发继续译码，直到结束

本章完

树和二叉树