数据结构-树

树的基本概念 定义

树（Tree）是n（n>=0）个结点的有限集。n=0时成为空树。
在任意一个非空树中：有且仅有一个特定的称为根（Root）的结点；n>1时，其余结点可分为m（m>0）个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。
ps：

1. 根结点是唯一的。
2. 子树的个数没有限制，但它们一定互不相交。

结点的分类

1. 结点拥有的子树数称为结点的度（Degree）。
2. 度为0的结点称为叶结点（Leaf）或终端结点；度不为0的结点称为非终端结点或分支结点。除根结点外，分支结点也称为内部结点。
3. 数的度是树内各结点的度的最大值。

结点间的关系

1. 结点的子树的根称为该节点的孩子，相应的，该结点称为孩子的双亲。
2. 同一个双亲的孩子之间互称兄弟。
3. 结点的祖先是从根到该结点所经分支上的所有结点。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。

其他相关概念

1. 节点的层次（Level）从根开始定义，根为第一层，根的孩子为第二层。若某结点在第l层，则其子树就在第l+1层。
2. 其双亲在同一层的结点互为堂兄弟。
3. 树中结点的最大层次称为树的深度（Depth）或高度。
   
4. 如果将树中结点的各子树看成从左至右的有序次的、不能互换的，则称该树为有序树，否则称为无序树。
5. 森林（Forest）是m（m>=0）棵互不相交的树的集合。对于树中的每个结点而言，其子树的集合即为森林。

树的储存结构 双亲表示法

以一组连续空间储存树的结点，同时在每个结点中，附设一个指示器指示其双亲结点在数组的位置。

#define MAX_TREE_SIZE 100

typedef int ElemType;

typedef struct PTNode//结点结构
{
	ElemType data;
	int parent;//双亲位置
}PTNode;

typedef struct//树结构
{
	PTNode nodes[MAX_TREE_SIZE];
	int r, n;//根的位置和结点数
}PTree;

孩子表示法

每个结点有多个指针域，其中每个指针指向向一棵的根结点，通常把这种方法叫做多重链表表示法，这种方法可以提高对空间的利用效率，但是由于要维护结点的度，会带来时间上的浪费。
而孩子表示法就是把每个结点的孩子结点排列起来，以单链表作储存结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序储存结构，存放进以为数组中：

#define MAX_TREE_SIZE 100

typedef int TElemType;

typedef struct CTNode//孩子结点
{
	int child;
	struct CTNode *next;
}*childPtr;
typedef struct//表头结点
{
	TElemType data;
	childPtr firstChild;
}CTBox;
typedef struct//树结构
{
	CTBox nodes[MAX_TREE_SIZE];//结点数组
	int r, n;//根的位置和结点数
}CTree;

孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

typedef struct CSNode
{
	TElemType data;
	struct CSNode *firstChild, *rightSib;
}CSNode, *CSTree;

这种表示法最大的好处就是可以表示成二叉树的形式。

二叉树

二叉树（Binary Tree）是n（n >=0）个结点的有限集合，该集合或则为空集（空二叉树），或者有一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

特点

1. 每个结点最多有两颗子树，所以二叉树中不存在大于2的结点。
2. 左子树和右子树是有顺序的，次序不可以任意颠倒。
3. 即使树中某结点只有一颗子树，也要区分它是右子树还是左子树。

特殊二叉树

1. 斜树：所有结点都只有左子树的二叉树叫作左斜树，所有结点都只有右子树的二叉树叫作右斜树，这两者统称为斜树。
2. 满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
3. 完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号为i（1<=i<=n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。
   完全二叉树的一些特点：
   1、 叶子结点只能出现在最下两层
   2、最下层叶子一定集中在左部连续的位置
   3、倒数二层，若有叶子结点，一定都在右部连续位置
   4、如果结点的度为1，则该结点只有左孩子，即不存在只有右子树的情况
   5、同样结点数的二叉树，完全二叉树的深度最小。

二叉树的性质

1. 在二叉树的第i层至多有2^i-1 个结点（i>=1）
2. 深度为k的二叉树至多有2^k - 1个结点（k>=1）
3. 对于任何一棵二叉树T，如果其终端结点数为n₀，度为2的结点数为n₂，则n₀=n₂+1 。
   ps：想要让终端结点数+1，那么度为2的结点一定也会+1（只增加左子树或者右子树是不会导致终端结点增加的）
4. 具有n个结点的完全二叉树的深度为[log₂ n]+1（[x]表示不大于x的最大整数）
5. 如果对一棵有n个结点的完全二叉树（其深度为[log₂ n]+1）的结点按层序编号（从第1层到第[log₂ n] 层，每层从左到右），对任一结点j（1<=i<=n）有：
   （1）如果i = 1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点[i/2]。
   （2）如果2i>n，则结点i无左孩子（结点i为叶子的左结点）；否则其左孩子是结点2i。
   （3）如果2+i>n，则结点i无右孩子；否则其右孩子是结点2*i+1.

储存结构 顺序储存结构

顺序储存即直接按照其在完全二叉树中的序号在对应的数组位置中存放相应的数据。
顺序储存结构通常只用于完全二叉树。

二叉链表

将二叉树结点空间设置为一个数据域和两个指针域。

typedef struct BiTNode
{
	ElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTNode;

遍历二叉树

二叉树的遍历（traversing binary tree）是指从根节点出发，按照某种次序依次访问二叉树中的所有结点，使得每一个结点被访问一次且仅被访问一次。

前序遍历

void PreOrderTraverse(BiTree T)
{
	if(T == NULL)
		return 0;

	printf("%d", T->data);//这里是对结点的 *** 作，可以更换所需的函数
	PreOrderTraverse(T->lchild);
	PreOrderTraverse(T->rChild);
}

中序遍历

void PreOrderTraverse(BiTree T)
{
	if(T == NULL)
		return 0;

	PreOrderTraverse(T->lchild);
	printf("%d", T->data);//可替换为其他对二叉树的 *** 作
	PreOrderTraverse(T->rchild);
}

后序遍历

void PreOrderTraverse(BiTree T)
{
	if(T == NULL)
		return 0;

	PreOrderTraverse(T->lchild);
	PreOrderTraverse(T->rchild);
	printf("%d", T->data);
}

二叉树的建立

//#表示空树
void CreateBiTree(BiTree *T, char *str)
{
	ElemType ch;

	scanf("%c", &ch);
	ch = str[index++];

	if(ch == '#')
		*T = NULL;
	else
	{
		*T = (BiTree)malloc(sizeof(BiTNode));
		if(*T)
			exit(OVERFLOW);
		(*T)->data = ch;//生成根结点
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
}

线索二叉树(以中序遍历)

我们将对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化；把这种指向前驱和后继的指针成为线索，加上线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。
如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么就可以考虑采用线索二叉树。

线索二叉树的实现

为了知道某一结点的lchild时指向它的左孩子还是前驱，rchild是指向右孩子还是后继，因此设置两个标志域ltag和rtag，其存放数字0或1数字型布尔型变量（是0则指向孩子，是1则指向前驱/后继）

储存结构：

typedef char TElemType;
typedef enum {Link, Thread} PointerTag;
//Link==0表示指向左右孩子指针，Thread==1表示指向前驱或后继的线索

typedef struct BiThrNode{
	TElemType data;

	struct BiTheNode *lchild, *rchild;
	PointerTag LTag;//左右标志
	PointerTag RTag;
}BiThrNode, *BiThrTree;

中序遍历线索化的递归函数代码：

BiThrTree pre;//始终指向刚刚访问过的结点

void InThreading(BiThrTree p)
{
	if(p)
	{
		InThreading(p->lchild);//递归左子树线索化
		if(!p->lchild)//没有左孩子
		{
			p->LTag = Thread;//前驱线索
			p->lchild = pre;//左孩子指针指向前驱
		}
		if(!p->rchild)//没有右孩子
		{
			pre->RTag = Thread;
			pre->rchild = p;//前驱右孩子指针指向后继（当前结点p）
		}
		pre = p;
		InThreading(p->rchild);
	}
}

判断后继时：因为此时p结点的后继还没有访问到，因此只能对它的前驱结点pre的右指针rchild作判断，if（！pre->rchild）表示如果为空，则p就是pre的后继，于是pre->rchild=p并且设置pre->RTag= Thread，完成后继结点的线索化。
线索化二叉树时，令二叉树中序序列中的第一个结点的lchlid指向头结点、最后一个结点的rchild指向头结点，使得我们既可以从第一个结点起顺后继进行遍历或顺最后一个结点起顺前驱进行遍历。

遍历代码：

Status InOrderTraverse_Thr(BiThrTree T)
{
	BiThrTree p;
	p = T->lchild;
	while(p != T)
	{
		while(p->LTag == Link)//当LTag==0时循环到中序序列的第一个结点
			p = p->lchild;

		printf("%c", p->data);//结点的 *** 作
		while(p->RTag == Thread && p->rchlid != T)//结点有后继，访问后继
		{
			p = p->rchild;
			printf("%c", p->data);
		}
		p = p->rchild;//当该结点无后继指针时，则证明其有右子树，就直接访问其右子树
	}
	return OK;
}

哈夫曼树

带权路径长度WPL最小的二叉树称做二叉树，也可以叫做最优二叉树。

1. 从树中的一个结点到另一个结点之间的分支结构构成两个结点之间的路径，路径上的分支数目称做路径长度。
2. 树的路径长度就是从树根到每一结点的路径长度之和。
3. 如果结点带权，则将权与不带权时的路径长度相乘得到结点的带权的路径长度。

如何构造哈夫曼树

二叉树b的WPL=53+153+402+302+10*2=220
构造哈夫曼树步骤：

1. 先把有权值的叶子结点从小到大排列成一个有序序列，即A5，E10，B15，D30，C40
2. 取两个最小权值的结点作为一个新结点N₁ 的两个子节点（较小的为左孩子），新结点的权值为两个叶子结点权值的和。
3. 将N₁ 替换A与E，插入有序序列中，保持从小到大的序列，即N₁ 15，B15， D30，C40。
4. 重复步骤二，得到新结点N₂ 。
5. 又将N₂ 替换N₁ 和B插入序列。
6. 重复步骤二，得到新结点N₃ 。
7. 将N₃ 替换N₂和D，插入序列。
8. 重复步骤二，最终得到哈夫曼树。即上图二叉树a。
   哈夫曼树实际上就是把带权值的结点置为无左右子树的叶子结点。

此时二叉树a的WPL=401+302+153+104+5*4=205比二叉树b还要少，显然a才是最优的哈夫曼树。
（不过二叉树a在每次判断时都要比较两次，实际上总体性能不如b）

哈夫曼编码

哈夫曼研究出这种最优二叉树是为了解决当年远距离通讯的数据传输的最优化问题。

一般地，设需要的编码字符集为{d₁，d₂，…，d_n}，各个字符在电文中出现的次数或频率的集合为{W₁，W₂，…，W_n}，以d作为叶子结点，将W作为对应叶子的结点的权值来构造一棵哈夫曼树。规定哈夫曼树的左分支为0、右分支为1，则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应的字符编码，这就是哈夫曼编码。