前言：树型结构是一类重要的非线性结构,其特点是结点之间有分支,并具有层次关系。

1.1 基本概念

1.1.1 树

        树是由n(n≥１)个有限结点组成的一个具有层次关系的集合, 把它叫作“树”是因为它看起来像一棵倒挂的树,也就是说树是根朝上,而叶朝下的。如图所示：

        它具有以下的特点：
            ① 每个结点有零个或多个子结点;
            ② 每个子结点只有一个父结点;
            ③ 没有前驱的结点为根结点;
            ④ 除了根结点外,每个子结点可以分为许多个不相交的子树。

        为方便描述树的特点，先列出将会涉及到的树的基本概念：
            ①结点的度：一个结点含有的子树个数；
            ②树的度：一棵树中，最大的结点的度；
            ③叶结点（终端结点）：度为0的结点；
            ④分支结点（非终端结点）：度不为0的结点；
            ⑤孩子结点：一个结点的子树的根结点；
            ⑥双亲结点（父结点）：在含有孩子的结点中，该结点称为孩子结点的双亲结点；
            ⑦兄弟结点：具有相同双亲的结点；
            ⑧祖先节点：从根到该结点所经分支上的所有结点；
            ⑨子孙结点：以某结点为根的子树中任意结点；
            ⑩节点的层次：从根开始定义，根为第一层，根的孩子为第二层，以此类推。如下图所示：
                
            ⑪树的高度（深度）：树中结点的最大层次；
            ⑫路径：从根结点到某一结点的一条通道；
            ⑬路径长度：路径经过的边的个数。如下图所示：
                

1.1.2 二叉树

        1.综述：二叉树是每个结点最多有两个子树的有序树，通常子树的根被称为“左子树”和“右子树”。如下图所示。二叉树是一种最简单的树结构，任何树都可以简单转换为二叉树。
            
        2.树和二叉树的区别
            ①树的结点个数至少为1，而二叉树的结点个数可以为0；
            ②树中结点的最大度数没有限制，而二叉树结点最大度数为2；

        3.两种特殊的而二叉树
            （1）满二叉树
                满二叉树中所有的叶节点都在最后一层，而其他分支结点的度数都为2。示例如下：
                    
            （2）完全二叉树
                若一个二叉树扣除其最后一层后变成一个满二叉树，且最后一层的所有结点都向左靠齐，则称该二叉树为完全二叉树。示例如下：
                    
            ★满二叉树一定为完全二叉树，完全二叉树不一定为满二叉树

        3.二叉树常见的性质
            性质1    一颗非空二叉树的第i层上最多有2^i-1^个结点（i≥1）
            性质2    深度为h的二叉树最多有2^h^-1个结点（h＞1）
            性质3    对于任何一棵二叉树T，如果其终端结点数为n~0~，度为2的结点数为n~2~，则n~0~=n~2~+1
            性质4    若一个正则二叉树（只有度为0和2结点的二叉树）中有n个叶子结点，则该二叉树结点总数为log~2~n（由 性质2 推导）
            性质5    对于具有n个结点的完全二叉树，如果如果按照从上到下、同一层次上的结点按从左 到右的顺序对二叉树中的所有结点从1开始顺序编号,则对于序号为i的结点,有
                ① 如果i＞1,则序号为i的结点其双亲结点的序号为[i/2] ([i/2] 表示对i/2的值取整); 如果i＝1,则结点i为根结点,没有双亲
                ② 如果2i＞n,则结点i无左孩子(此时结点i为终端结点);否则其左孩子为结点2i
                ③ 如果2i＋1＞n,则结点i无右孩子;否则其右孩子为结点2i＋1

1.1.3 森林

        由m（m≥0）棵互不相交的树构成的集合称为森林。如下图所示，该森林由三棵树所构成：
            

1.2 基本操作

1.2.1 树的遍历

        1.前序遍历
            ①访问根结点；
            ②按照从左到右的顺序前序遍历根结点的每一棵子树。
        2.后序遍历
            ①按照从左到右的顺序后序遍历根结点的每一棵子树；
            ②访问根结点。
        3.层序遍历（广度遍历）
            从树的第一层（也就是根结点）开始自上而下逐层遍历，每一层按照从左到右的顺序逐个访问结点。

    下图展示了按照这三种遍历方式所对应的遍历结果：
        

1.2.2 二叉树的遍历

        1.前序遍历
            ①访问根结点
            ②前序遍历访问根结点的左子树
            ③前序遍历访问根结点的右子树
        2.中序遍历
            ①中序遍历访问根结点的左子树
            ②访问根结点
            ③中序遍历访问根结点的右子树
        3.后序遍历
            ①后序遍历访问根结点的左子树
            ②后序遍历访问根结点的右子树
            ③访问根结点
        4.层序遍历
            按照从上到下，同一层次从左到右的顺序访问二叉树

        下图展示了一棵二叉树四种遍历方式的结果：
            
    ★由二叉树的前序（后序)序列和中序序列可以唯一确定一棵二叉树，但是只由前序序列和后序序列不能确定一棵二叉树。

1.2.3 森林的遍历

        1.前序遍历
            若森林非空，则：
            ①访问森林中第一棵树的根结点
            ②前序遍历第一棵树中根结点的每一棵子树
            ③前序遍历除第一棵树外的其他树
        2.后序遍历
            若森林非空，则：
            ①后序遍历第一棵树的根结点的各个子树
            ②访问第一棵树的根结点
            ③后序遍历除第一棵树外的其他树

        下图给出了一个三棵树的森林的两种遍历结果：
            
        ★根据森林，树和二叉树的关系，可以得知：
            ①前序遍历森林＝前序遍历该森林对应的二叉树
            ②后序遍历**森林＝中序遍历该森林所对应的二叉树
            ③前序遍历树＝前序遍历该树所对应的二叉树
            ④后序遍历树＝中序遍历该树所对应的二叉树**

1.2.4 树、森林和二叉树的转换

        1.树、森林转换成二叉树
            ①在所有兄弟之间加一条线
            ②对每个结点，去掉该结点和除长子外与其他孩子的连线
        树转换为二叉树如下图所示：
            
        森林转换成二叉树如下图所示：
            
        2.二叉树转换成树、森林
        若结点x是双亲y的左孩子，则把x的右孩子、右孩子的右孩子都与y连起来，最后去掉双亲到右孩子的连线。如图所示：
            

1.3 存储结构

1.3.1 数的存储结构

基本要求：
    ①能够存储各结点信息；
    ②唯一的表示各结点之间的逻辑结构——父子关系

1.双亲表示法
    （1）原理：利用一维数组来表示树,一维数组的每个元素表示树的结点,其中包括结点的数据和该结点 的双亲在数组中的下标；数组中的第一个元 素表示根结点,该结点无双亲,因此parent域用-1表示,其他结点按照层序存储.如结点B、 C、D 的双亲结点是下标为0的根结点,其parent域用0表示。
        

    （2）C++描述

1
2
3
4
5
6
7
8
9

template < class T > struct pNode //结点的C++描述
{
	T data;
	int parent;
};

#define MAXSIZE 1000
pNode< T > Tree[MAXSIZE]; //树的C++描述
int size; //树的总结点数

    （3）结点结构：
        
    （4) 优点：结构简单,查找结点的双亲或者祖先非常方便

2.孩子表示法
    （1）应用时需要查找当前结点的孩子,双亲表示法就会比较复杂。此时为了适应查找孩子结点的需求，可以使用孩子表示法
        
    （2)C++描述

1
2
3
4
5
6
7
8
9
10
11

struct CNode //孩子链表结点结构
{
	int child; //孩子结点在表头数组中的下标
	CNode* next; //指向下一个孩子结点
};

template < class T > struct CBNode //表头结点
{
	T data;
	CNode* firstchild; //指向第一个孩子结点
};

    （3）孩子表示法与双亲表示法正好相反,查找孩子结点很方便,但是查找双亲结点较为复杂

3.多重链表法
    （1）原理：多重链表法指每个结点包括一个结点信息域和多个指针域,每个指针域指向该结点的 一个孩子结点,通过各个指针域的值反映出树中各结点之间的逻辑关系。这种表示法中,树中每个结点有多个指针域,从而形成了多条链表。由于每个结点的孩子个数没有限制,各结点的度数又各异,可能会造成存储空间的浪费。例如,一棵度为k的 树,若其结点总数为n,则至少要浪费nk－n＋１个空指针域
        
    （2)缺点：不适合存储度数较大的树

4.孩子兄弟表示法
    （1）原理：孩子兄弟表示法又称二叉链表表示法,链表中的每个结点包含一个数据域和两个指针域, 其中,数据域用来存储结点数据;第１个指针域指向该结点的第一个孩子结点;第２个指针域指向该结点的第一个右兄弟。
        
    （2)C++描述

1
2
3
4
5
6

template < class T > struct TNode
{
	T data;
	TNode<T>* firstchild;
	TNode<T>* rightsib;
};

    （3） 优点：可以将任意复杂的树结构转换成二叉树,这样对树的研究就可以转化为对二叉树的研究,降低了问题的复杂程度

1.3.2 二叉树的存储结构

1.顺序存储结构：
        二叉树的顺序存储结构使用一维数组存储二叉树的结点,利用结点的存储位置来表示结点之间的关系。具体如下：
        （1）将二叉树按照完全二叉树编号;
        （2）其中无结点的位置使用NULL表示,结点则存储在一维数组相应的位置上。如下图所示：
        
        这种存储数据的方法逻辑简单但会造成空间的浪费,因此,该方法最适合存储完全二叉树

2.二叉链表
        （1）基本思想如下图所示：
        
        （2）结点结构：
        
        （3)C++描述：

1
2
3
4
5
6

template < class T > struct BiNode
{
	T data;
	BiNode<T>* lchild;
	BiNode<T>* rchild;
};

        二叉链表的存储方式和树的孩子兄弟表示法的存储结构完全相同,任何一棵复杂的树都可以容易地使用二叉链表的方式进行存储

3.三叉链表
        在二叉链表的存储方式下,从某结点出发可以直接访问到它的孩子结点,但要找到它的双亲,则必须从根结点开始搜索,最坏情况下,可能需要遍历整个二叉链表。所以, 在这种情况下,可以采用三叉链表来存储二叉树,以避免该问题的发生
        （1）结构：
        
        （2）结点结构：
        

        （3）C++描述：

1
2
3
4
5
6
7

template < class T > struct BiNode
{
	T data;
	BiNode<T>* parent;
	BiNode<T>* lchild;
	BiNode<T>* rchild;
};

1.4 二叉树的实现

1.4.1 二叉树的声明

        采用二叉链表作为存储结构的二叉树其简单的 C＋＋ 描述如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

template<class T> class BiTree
{
private:
	void Create(BiNode<T>* &R, T data[], int i, int n); //创建二叉树
	void Release(BiNode<T>* R); //释放二叉树
public:
	BiNode<T>* root; //根结点
	BiTree(T data[], int n); //构造函数
	void PreOrder(BiNode<T>* R); //前序遍历
	void InOrder(BiNode<T>* R); //中序遍历
	void PostOrder(BiNode<T>* R); //后序遍历
	void LevelOrder(BiNode<T>* R); //层序遍历
	~BiTree(); //析构函数
};

1.4.2 二叉树的关键算法

1.二叉树的创建
        建立二叉树有很多种方法,其中较为简单的就是使用顺序存储结构来建立二叉链表。以顺序存储结构为输入创建二叉树时,采用先建立根结点,再建立左右孩子的方法递归地建立用二叉链表表示的二叉树,其 C＋＋描述如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

template<class T>
void BiTree<T>::Create(BiNode <T>*& R, T data[], int i, int n) //i表示位置，从1开始
{
	if (i <= n && data[i - 1] != 0)
	{
		R = new BiNode<T>; //创建根结点
		R->data = data[i - 1];
		R->lchild = R->rchild = NULL;
		Create(R->lchild, data, 2 * i); //创建左子树
		Create(R->rchild, data, 2 * i + 1); //创建右子树
	}
}

template<class T> BiTree<T>::BiTree(T data[], int n)
{
	Create(root, data, 1, n);
}

        上述递归程序分解步骤如下,假设输入为下图所示的顺序存储结构表示的二叉树,则递归地建立用二叉链表表示的二叉树示意图如下图所示
        
２．二叉树前序、中序、后序遍历的实现
        由二叉树的前序遍历定义,结合递归,前序遍历的结果如下图所示。
        

         C＋＋算法描述如下:

1
2
3
4
5
6
7
8
9
10

template<class T>
void BiTree<T>::PreOrder(BiNode<T>* R)
{
	if (R != NULL)
	{
		cout << R->data; //访问结点
		PreOrder(R->lchild); //遍历左子树
		PreOrder(R->rchild); //遍历右子树
	}
}

         对于中序遍历,只需要把语句 cout << R->data; 移到语句 PreOrder(R->lchild); 之后即可;
         对于后续遍历,只需要把语句 cout << R->data; 移到语句 PreOrder(R->rchild); 之后即可。

3.层序遍历的实现
         二叉链表的层序遍历基本思想如下：
        
         具体描述如下：
         【1】若根结点非空，入队。
         【2】如果队列不空：
                  【2.1】队头元素出队；
                  【2.2】访问该元素；
                  【2.3】若该结点的左孩子非空，则左孩子入队；
                  【2.4】若该结点的右孩子非空，则右孩子入队。
         C++描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

template<class T>
void BiTree<T>::LevelOrder(BiNode<T>* R)
{
	BiNode<T>* queue[MAXSIZE];
	int f = 0; r = 0; //初始化空队列
	if (R != NULL) queue[++r] = R; //根结点入队
	while (f != r)
	{
		BiNode<T>* p = queue[++f]; //表头元素出队
		cout << p->data; //出队打印
		if (p->lchild != NULL) queue[++r] = p->lchild; //左孩子入队
		if (p->rchild != NULL) queue[++r] = p->rchild; //右孩子入队
	}
}

4.析构函数的实现
         二叉链表属于动态存储分配,因此,需要在析构函数中释放二叉链表的所有结点.为了防止内存泄漏,释放结点时应先释放该结点的左右子树,左右子树全部释放完毕后再释放该结点。采用后序遍历的方法，具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

template<class T>
void BiTree<T>::Release(BiNode<T>* R) //释放二叉树
{
	if (R != NULL)
	{
		Release(R->lchild); //释放左子树
		Release(R->rchild); //释放右子树
		delete R; //释放根结点
	}
}

template<class T> BiTree<T>::~BiTree() //释放二叉树
{
	Release(root);
}

1.5 Huffman树

1.5.1 Huffman树的定义与存储结构

1.Huffman树的定义
        哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。树的带权路径长度, 就是树中所有叶结点的权值乘上其到根结点的路径长度(若根结点为０层,叶结点到根结点的路径长度为叶结点的层数)之和
        
        图（C）所示的二叉树其带权路径长度最短,而且再也找不出比此二叉树带权路径长度更短的二叉树了,因此图（C)所示是一棵哈夫曼树

2.Huffman编码
        （1）Huffman编码根据字符出现的概率来构造平均长度最短的编码，是一种变长的编码。它的基本原理是频繁使用的数据用较小的代码代替，较少使用的数据用较大的编码代替，每个数据的代码不相同，但最终编码的平均长度最小。
        （2）变长的编码：Huffman编码得到的字符编码，其长度因符号出现的概率而有所不同。
        （3）Huffman编码的规则：从根结点到叶结点（包含原信息）的路径，向左孩子前进编码为0，向右孩子前进编码为1.也可以反过来规定
        示例：
        
        得到字符A、B、C、Z的编码分别为0、11、100、101.显然Huffman编码是前缀编码，即任何一个字符的编码都不是另一个字符编码的前缀。

3.Huffman树的存储结构
        以静态散链表来存储结点：

1
2
3
4
5
6
7

struct HNode
{
	int weight; //结点权值
	int parent; //双亲数组下标
	int LChild; //左孩子数组下标
	int RChild; //右孩子数组下标
};

        Huffman树是一棵正则二叉树（只有度为0或2的结点的二叉树）。根据二叉树的性质，一棵n个叶子的Huffman树共有2n-1个结点，可以用一个大小为2n-1的一维数组存放Huffman树的各个节点。
        如下图（a）所示的Huffman树有4个叶子结点，因此可以定义存储结构为：

1

HNode* HTree = new HNode[7];

        其存储内容如下图（b）所示，-1表示无孩子结点或双亲结点

        还需要设计Huffman编码表对每个结点进行存储。编码表中各元素的C++描述如下：

1
2
3
4
5

struct HCode
{
	char data;
	string code;
};

        其中，data存储结点的内存（这里假设其数据类型为char）。code数组存储结点对应的编码（这里采用string存储）。使用HCode类型定义一个一维数组，就可以存储所有结点的编码了。
        接下来就可以设计Huffman编码的相关算法了，如构造、编码、解码算法。其C++类描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Huffman
{
private:
	HNode* HTree; //Huffman树
	HCode* HCodeTable; //存储编码表
	int N; //叶子结点数量
	void code(int i, string newcode); //递归函数，对第i个结点编码
public:
	void CreateHTree(int a[], int n, char name[]); //创建Huffman树
	void CreateCodeTable(); //创建编码表
	void Encode(char* s, char* d); //编码
	void Decode(char* s, char* d); //解码
	~Huffman();
};

        其中，HTree存储Huffman树的结构，HCodeTable存储每个结点的编码内容。（假设要编码的数据和编码结果均为字符串类型）

1.5.2 Huffman树的构造

        构造Huffman树的方法就是Huffman算法，描述如下：
        将n个带权值的结点构成n棵二叉树的集合T，每棵二叉树只有一个根结点，其左右子树都为空：
        ①在T中选取两个根结点权值最小的二叉树作为左右子树，构成一棵新二叉树。其根结点的权值为左右子树根结点权值之和；
        ②在T中删除这两棵树，将新树加入T；
        ③重复①②操作，直到T中仅存一棵树，该树即Huffman树
        图示如下：

        生成这样的Huffman树的C++描述：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//输入参数a[]存储每种字符的权值，n为字符的种类，name为各个字符的内容
void Huffman::CreateHTree(int a[], int n, char name[])
{
	N = n;
	HCodeTable = new HCode[N];
	HTree = new HNode[2 * n - 1]; //根据权重数组a[0..n-1]初始化Huffman树
	for (int i = 0; i < N; i++)
	{
		HTree[i].weight = a[i];
		HTree[i].LChild = HTree[i].RChild = HTree[i].parent = -1;
		HCodeTable[i].data = name[i];
	}
	int x, y;
	for (int i = n; i < 2 * N - 1; i++) //开始建立Huffman树
	{
		SelectMin(x, y, 0, i); //从1~i中选出两个权值最小的结点的函数
		HTree[x].parent = HTree[y].parent = i;
		HTree[i].weight = HTree[x].weight + HTree[y].weight;
		HTree[i].LChild = x;
		HTree[i].RChild = y;
		HTree[i].parent = -1;
	}
}

1.5.3 Huffman编码表的构建

        本文采用向上而下递归的处理方式，对每一个结点进行编码。若子树的根结点是其父结点的左分支则编码“0”，若是右分支则编码“1”，递归处理直到叶子结点。
        生成编码表的C++描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void Huffman::code(int i, string newcode) //递归函数，对第i个结点编码
{
	if (HTree[i].LChild == -1)
	{
		HCodeTable[i].code = newcode;
		return;
	}
	code(HTree[i].LChild, newcode + "0");
	code(HTree[i].RChild, newcode + "1");
}

void Huffman::CreateCodeTable() //生成编码表
{
	code(2 * N - 2, "");
}

        如下图（a）所示的Huffman树，其对应编码表可以是下图（b）的结构

1.5.4 Huffman编、解码的实现

        通常,对一段信息进行哈夫曼编码时,需要对编码的数据进行两遍扫描.
（1）第一遍用来统计原数据中各字符出现的频率,利用得到的频率值创建哈夫曼树,并要把树的信息及编码表保存起来,以便解压时创建同样的哈夫曼树进行解压;
（2）第二遍根据第一遍扫描得到的哈夫曼编码表对原始数据进行编码,并把编码后得到的码字存储起来

1.编码
        生成编码表后，对于要编码的字符串，每读出一个字符，只要在编码表中找出对应编码即可；

2.解码
        其基本思想是将编码串从左到右逐位判别，直到确定一个字符。即从Huffman根节点开始，根据每一位是0或者1选择左分支或右分支，直到到达叶子结点，至此每一个字符解码结束。然后，再从根结点开始下一个字符的解码
        解码算法的C++描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void Huffman::Decode(char* s, char* d) //s为编码串，d为解码后的字符串
{
	while (*s != '\0')
	{
		int parent = 2 * N - 2; //根结点在HTree中的下标
		while (HTree[parent].LChild != -1) //如果不是叶子结点
		{
			if (*s == '0')
				parent = HTree[parent].LChild;
			else
				parent = HTree[parent].RChild;
			s++;
		}
		*d = HCodeTable[parent].data;
		d++;
	}
}