D5-树和二叉树

树是由n（n>=0）个元素构成的有限集合，该集合需要满足以下特征：

1.有且仅有一个被称为根的结点

2.除根结点外的其他结点被分为m个 互不相交 的有限集合，，每个集合又被称为一个树。

由此可见，树是一个递归结构。

树是非线性结构，在线性表中，除头结点和尾结点外，每个结点有一个前驱和一个后继，但在树中，除根结点外，每个结点有一个前驱，n个后继。

结点拥有的子树的个数称为结点的度，度为0的结点称为叶子或终端结点，度不为0的结点称为分支节点，树的度为树内部各个结点的度的最大值。结点的子树的根称为该结点的孩子，该结点称双亲，同一个双亲的孩子之间互称兄弟。结点的祖先是从该结点到根所经的全部结点，反之，子孙指以某结点为根的子树中的任意结点。

结点的层次从根开始定义，根为第一层，根的孩子为第二层，树的最大层数称树的深度或高度。

若树中结点各子树看成从左到右有次序的，则称有序树，反之称无序树。森林指m棵互不相交树的集合，在森林中加一个根结点就变成了树，将树的根节点去掉，将得到森林。

二叉树：每个结点至多只有两棵子树，且有左右之分，不能随意改变，是有序树。

二叉树的五种基本形态如下

需要知道：一个度为2的有序树并不是二叉树。因为若去掉有序树的第一子树后，第二子树会顺延成为第一子树，而在二叉树中，会形成左子树为空，只存在右子树的情况。

若树高为i，结点个数为2^i-1的二叉树称为满二叉树，对满二叉树的结点从上到下从左到右编号，当一个二叉树的编号与满二叉树可以一一对应时，称完全二叉树。

性质：

1.对第i层，结点的个数最多为2^(i-1)

2.对树高为k，结点总个数最多为2^k-1；

3.若终端结点数为a，度为2的结点数为b，那么a=b+1；由满二叉树依次去掉叶结点易求出

4.具有n个结点的完全二叉树深度为[log n]+1；

5.若存在第i个结点，则它的双亲结点为i/2，左孩子为2*i或无，右孩子为2*i+1或无。

二叉树的储存方法：

1.顺序存储

2.二叉链表

3.三叉链表

4.线索

1.顺序存储：即将二叉树存储在一个一位数组中，第i个结点的左右孩子分别存储在第2*i位和2*i+1位，适用于完全二叉树的存储，最坏情况下，有k个元素，需要2^k-1个空间，较简单不过多叙述

2.二叉链表：每个结点存在一个数据域，两个指针域，分别指向左孩子和右孩子

3.三叉链表：每个结点存在一个数据域，三个指针域，分别指向左孩子、右孩子和根结点

假设左孩子为L，右孩子为R，根结点为D，且访问子树的顺序为先左后右，那么有三种访问顺序即RLD,LRD,LDR，分别称为先序遍历，中序遍历和后序遍历。这三种遍历方式都可以通过递归实现，并且代码简单，不叙述。

使用先序、中序、后序遍历可以实现对树的不同 *** 作

首先使用二叉链表对树定义

typedef struct BITNode {
	int data;
	struct BITNode* lchild, * rchild;
}BITNode, * BITree;

先序遍历统计叶结点个数

void countleaf(BITNode T, int& count) {
	if (T) {
		if (!T.lchild && !T.rchild)//左右子树都为空时
			count++;

		countleaf(T.lchild, count);
		countleaf(T.rchild, count);
	}
}
//先对根结点统计，再依次对下层叶结点统计，为先序遍历

解释一下函数参数中取地址符的用处：

当函数形参为int &k时，在函数中对k进行 *** 作，比如说赋值，那么主函数中相应的主对象的值也会跟着改变。
相当于一个静态的指针变量，但是不需要加上间接访问符*且不会开辟临时空间，直接就是对k本身 *** 作，地址不可修改。

 后序遍历求二叉树的深度

int depth(BITree T) {
	if (!T) {
		depthval = 0;
	}
	else {
		depleft = depth(T->lchild);
		depright = depth(T->rchild);
		depthval = 1 + depleft > depright ? depleft : depright;
		return depthval;
	}
}
//必须在左右子树的基础上求二叉树的深度

后序遍历复制二叉树

BITNode* GetNode(int item, BITNode* lptr, BITNode* rptr) {
	if (!(T = (BITNode*)malloc(sizeof(BITNode*))));
    //记得给T申请空间！！！！
    
    T.data = item;
	T.lchild = lptr;
	T.rchild = rptr;
	return T;
}//建立一个二叉树的结点

BITNode* CopyNode(BITNode *T) {
	if (!T)
		return NULL;

	if (T->lchild)
		newlptr = CopyNode(T->lchild);
	else
		newlptr = NULL;
	if (T->rchild)
		newrptr = CopyNode(T->rchild);
	else
		newrptr = NULL;

	newNode = GetNode(T->data, T->lchild, T->rchild);

	return newNode;
}

线索二叉树

遍历一个二叉树可以得到线性序列，每个元素都有前驱和后继，若在每个结点增添tag用以说明该结点是否指向前驱和后继，tag称线索，该链表称线索链表，二叉树称线索二叉树。线索二叉树结构体定义如下

typedef enum Pointertag{Link,Thread};
//枚举类型自动从0开始，向后每位加一，因此Link为0，Thread为1

typedef struct BiThrNode {
	Pointertag LTag, RTag;
	int data;
	struct BiThrNode* lchild, * rchild;
}BiThrNode, * BiThrTree;

若结点有左右子树，则Tag值为0，若指针指向前驱后继，Tag值为1。

线索化函数如下

BiThrTree pre;//前驱指针，始终指向当前结点的前驱

void InThreading(BiThrTree p) {
	if (p) {
		InThreading(p->lchild);
		//若结点左子树为空，即指针应指向前驱后继而不指向子树，tag标志位为1，
        //正好将左子树的地址赋给pre作为前驱
		if (!p->lchild) {
			p->LTag = Thread;
			p->lchild = pre;
		}
		//此时需要将p和pre互为前驱后继，上面已经实现了前驱，此时实现后继
		//若pre右子树为空，即指针标志位为1==Thread，将pre右子树的地址赋给p
        //实现p成为pre的后继
		if (!pre->rchild) {
			pre->RTag = Thread;
			pre->rchild = p;
		}
		pre = p;//使得pre始终指向p的前驱

		InThreading(p->rchild);
	}
}

建立线索二叉树之前，我们要了解建立它的原理。我们是先将一棵二叉树视作双向循环链表，之后才将其视为一棵树。对于一棵二叉树，如果我们对他进行中序遍历，那么第一个遍历的结点一定是最左下的结点，最后一个遍历的结点是最右下的结点，每个结点都一定有前驱和后继。如果我们建立一个结点，使它的左孩子指向根结点，右孩子指向中序遍历时最后一个结点，同时中序遍历的第一个结点的左孩子和最后一个结点的右孩子也指向他，这样就建立了一个双向循环链表思想的树，之后我们只需对每个结点判断是否有左右子树并对其相关的指针域赋1或0。为了便于实现这个 *** 作，设置一个指针pre指向当前结点的上个结点。

//遍历算法，visit视为访问数据的函数
int InOrder_Thr(BiThrTree& T, Visit(int e)) {
	BiThrTree p;
	p = T->lchild;

	while (p != T) {
		while (p->LTag == Link)
			p = p->lchild;
		if (!Visit(p->data)) {
			printf("ERROR");
			return 0;
		}
		while (p->RTag == Thread && p->rchild != T)
			p = p->rchild;
		p = p->rchild;
	}
}

//建立中序遍历二叉树算法
int InOrderThreading(BiThrTree& Thrt, BiThrTree T) {
	//Thrt为根结点,pre为前缀指针，T指针访问不同结点
	BiThrTree pre;
	Thrt->RTag = Thread, Thrt->LTag = Link;
    //建立根节点的左右指针

	T->rchild = Thrt;
    //右指针回指，此时T就是中序遍历最后的结点，它的右子树应当指向根结点，
    //若子树存在再改变T的右子树指向的位置

	if (!T)
		T->lchild = Thrt;
    //若树T无左右子树，T既是中序遍历的第一个结点又是最后一个结点，左右子树均应回指

	else {
		T = Thrt->lchild;
		pre = Thrt;

		InThreading(T);//递归线索二叉树T

		//线索化最后一个结点，最后一个结点的RTag必为Thread，要指向根结点
		pre->rchild = Thrt;
		pre->RTag = Thread;

		//有了最后一个结点，它的右子树指向的地址应该为根结点
		Thrt->rchild = pre;
	}
	return 1;
}

树的存储结构分为：双亲表示法，孩子表示法，孩子兄弟表示法

其结构体定义及解释如下

//双亲表示法
//容易找到树的根，但不容易求叶结点，需要遍历整个树

#define MAX_SIZE 100
typedef struct PTNode {
	int data;
	int parent;//储存在数组中的位置
}PTNode;
typedef struct PTree {
	PTNode node[MAX_SIZE + 1];//该数组中所有元素都为PTNode型
	int r, n;//用以存储根的位置和结点个数
}PTree;

 在上图所示树中，已知根结点R位置为-1，它的孩子们在数组中存储位置为node[1、2、3]，对应的parent位置域都为0，即R的位置，下面的叶结点同理可得。

//孩子兄弟表示法
//易于实现各种 *** 作，假如要找结点的第i个孩子，只需要先找该结点指针指向的第一个孩子结点，
//再对孩子结点寻找i-1步后的兄弟结点

typedef struct CSNode {
	int data;
	struct CSNode* firstchild, * nextsibling;
    //分别存储第一个子结点和该结点的第一个兄弟结点
}CSNode, * CSTree;

//孩子表示法
//将每个结点的孩子结点组成一个线性表，且以单链表作为存储结构每个链表的头指针又可以组成一个链表
//便于进行叶子结点的 *** 作，如遍历叶结点，但不适用于寻找双亲结点

数据类型定义如下
#define MAXSIZE_TREE_SIZE 100
//单链表，存储每个结点的孩子结点
typedef struct CTNode {
	int child;
	struct CTNode* next;
}*ChildPtr;

//存储一个链表的头指针和数据
typedef struct {
	int data;
	ChildPtr firstchild;
}CTBox;

//提供一个一维数组，存储所有链表的头指针
typedef struct {
	CTBox node[MAXSIZE_TREE_SIZE + 1];
	int r, n;//存储结点的位置和个数
}CTree;

森林转化成二叉树

设F={T1,T2......}是一个森林，那么若将它转化为二叉树，二叉树的根结点为T1，根结点的左子树为T1的子树森林组成的二叉树，根结点的右子树为森林{T2,T3...}组成的二叉树

二叉树B=（root，LB,RB）转化为森林同理，逆推即可，root为T1，LB为T1的子树，RB为T2、T3...组成的森林。

哈夫曼树

又称最优树，不一定为二叉树，定义为带权路径长度最短的树。路径指的是两个结点间的分支，路径长度就是两个结点间的分支数目。树的路径长度指的是根结点到每一个叶子结点的路径长度之和。结点的带权路径长度指的是结点的到树根的路径长度与该结点所带权的乘积。树的带权路径长度指的是所有叶子结点带权路径长度之和，记为WPL.。WPL最小的树称为哈夫曼树。

构建哈夫曼树的方法是由下自上构建，先找到两个带权最小的结点，将其组合成一棵二叉树，二叉树根节点的权值是这两个结点权值相加，之后在集合中去除两棵子树，添加这棵新增的二叉树，重复这个步骤，直到只剩下一棵树，就是哈夫曼树。

那么我们可以知道哈夫曼树的几个特点：若哈夫曼树有n个叶结点，那么它有2n-1个结点；权值越大的叶结点，离根节点越近；哈夫曼树是正则二叉树，不存在度为1的结点；哈夫曼树的形状不唯一，任意结点的左右子树交换位置仍为哈夫曼树。

我们在传送数据时，需要将数据转化为二进制码传输，传输的数据字符可能相同，也可能不同。我们用二进制码表示字符时可以用等长度的二进制码表示，也可以用不等长的码来表示。若用不等长度的码，即用不同位数的0或1表示，传输总长度显然小于使用等长二进制码。例如，传输ABCD，我们可以假设A=0,B=01,C=10,D=1，那么ABCD=001101,。但是这样做有一个缺陷，就是字符可能被误读，001101也可能被读作AADDAD、AADCD，对于更长的编码来说，只会错的更多。因此为了解决这个问题，借助哈夫曼树提出了哈夫曼编码。

哈夫曼编码的核心思想是以字符出现的频率作为权值，将字符编成一个哈夫曼树，并设一个结点的左路径编码为0，右路径编码为1，这样就可以得到所有字符的表示方法，并且可以保证每个字符的前缀一定不会是其他字符，这种编码方式是前缀编码。

代码如下

typedef struct {
	int weight;//权值
	unsigned int parent, lchild, rchild;
}HTNode, * HuffmanTree;
typedef char** HuffmanCode;//动态存储哈夫曼编码

//Select函数实现在HT中，查找从1到i-1最小的两个值的序号赋给s1、s2
//s1的值小于s2，s1、s2的parent为0
void Select(HuffmanTree& T, int i, int s1, int s2) {
	if (i <= 1)
		return;
	int min1 = T->weight, min2 = T->weight;

	//可能一个数组中有相同的权值，pos保证s1s2不是同一个权值
	int pos1 = 1, pos2 = 1;
	int j;
	for (j = 1; j <= i; j++, T++) {
		if (T->weight < min1) {
			min1 = T->weight;
			pos1++;
		}
	}
	for (j = 1; j <= i; j++, T++) {
		if (T->weight < min2 && (pos2 + 1) != pos1) {
			min2 = T->weight;
			pos2++;
		}
	}
	s1 = pos1, s2 = pos2;
}

//w存放n个字符的权值
void HuffmanCoding(HuffmanTree& HT, HuffmanCode& HC, int* w, int n) {
	if (n < 1)
		return;
	//不需要返回值，只需告知该函数已结束

	//二叉树总结点数为m
	int m = 2 * n - 1;
	HuffmanTree p;
	int i;

	//动态分配内存
	HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));

	//为叶结点赋权值，为其他结点赋0
	for (p = HT, i = 1; i <= n; i++, p++, w++)
		*p = { *w,0,0,0 };//大括号用于对结构体赋值
	for (; i <= m; i++, p++)
		*p = { 0,0,0,0 };

	//开始构建哈夫曼树
	int s1, s2;
	for (i = n + 1; i <= m; i++) {
		Select(HT, i - 1, s1, s2);
		HT[s1].parent = i, HT[s2].parent = i;
		HT[i].lchild = s1, HT[i].rchild = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;
	}

	HC = (HuffmanCode)malloc((n + 1) * sizeof(char*));

	//cd储存一个编码
	char* cd = (char*)malloc(n * sizeof(char));

	//重要！！！//存储结束标志，cd数组从0开始存储，存储n-1个元素而非n个
    //因为对有n个叶子结点的哈 夫曼树最长只有n-1个路径可以编码，即树的路径长度为n-1
	cd[n - 1] = '

'; for (i = 1; i <= n; i++) { //cd数组结束位 int start = n - 1; int c, f; //i既是当前求哈夫曼编码叶子结点的编号，又是对每个叶子结点从叶子求编码到树根的标志， //将HT树当做一维数组存储，叶子结点占据HT数组的前n位，其余结点占据HT数组的n+1到m位 //parent作为标志位，指示着当前结点在二叉树中连接的上一层的结点的结点位置 //c=i语句是求叶子结点的双亲结点位置，括号内第三个语句c=f是求叶子结点双亲的双亲的位置 这样求到树根结点 //f!=0说明已经求到根结点，即当前结点的parent为0，HT数组中哪些元素的parent为0呢，就 是从第n+1到第m个元素 for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent) { if (HT[f].lchild == c) cd[--start] = '0'; if (HT[f].rchild == c) cd[--start] = '1'; } HC[i] = (char*)malloc((n - start) * sizeof(char)); //将cd形成的第i个叶子结点的编码复制到HC[i] strcpy(HC[i], &cd[start]); } free(cd); }