树

一.树的基本概念

结点：包含一个元素及若干指向子树的分支。
根结点、终端结点、其他结点（仅有1个前驱，多个后继）

结点的度：一个结点所拥有的子树的个数

树的度：树中各结点度的最大值

叶子结点：度为0的结点
分支结点：度不为0的结点


路径：如果树的结点序列 {n1, n2, …, nk} 满足如下关系：结点 ni 是结点 ni+1 的双亲（其中，1≤i<k），则把 n1、n2、…nk 称为一条由 n1 至 nk 的路径 。
路径长度：路径上经过边的个数


祖先：如果从结点 x 到 y 有一条路径，那么结点 x 称为 y 的祖先
子孙：如果从结点 x 到 y 有一条路径，那么结点 y 称为 x 的子孙

结点层次：在一棵树中，根结点的层次为 1，其他结点的层次等于其双亲结点的层次加 1
树的深度：树中所有结点的最大层次，也称高度

有序树：如果将树中每个结点各子树看成是从左到右有次序的（即不能互换），则称该树为有序树。
无序树：如果将树中每个结点各子树看成是从左到右无次序的（即可以互换），则称该树为无序树
在数据结构中一般讨论的都是有序树

森林：m(m>=0)棵不相交的树的集合

同构：对两棵树，如果通过对结点适当地重命名，就可以使这两棵树完全相等（结点的位置完全相同），则称这两棵树同构
如图：此两树同构

二.树的遍历

1.先序遍历

访问顺序：根——>左子树——>右子树

2.后序遍历

访问顺序：左子树——>右子树——>根

3.中序遍历

访问顺序：左子树——>根——>右子树

4.层序遍历

• 从树的第一层（即根结点）开始，自上而下逐层遍历
• 在同一层中，按从左到右的顺序对结点逐个访问
  

三.树的存储表示和操作实现

1.双亲表示法

以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲在数组中的位置。采用这种存储结构的树称为双亲顺序表。
实际上是一个静态链表
存储形式如下：


双亲顺序表的类型定义

#define Tree_Size 100		// 树中结点的最大个数
typedef struct PTNode
{ ElemType   data;		// 树中结点的数据信息int	  parent;	// 该结点双亲在数组中的下标
}PTNode; 
typedef struct  { PTNode	tnode[Tree_Size];	// 存放树结点的数组int		num;		// 树中的结点个数
} PTree; 

• 适合求指定结点的双亲或祖先（包括根）的操作
• 如果求指定结点的孩子或其他后代时，则需要遍历整个结构

在双亲顺序表中求结点双亲的数据信息：
假设T中值为e的结点不多于1个：

• 如果e不存在，则给出相应信息
• 如果e是根结点，表示没有双亲，则给出相应信息
• 如果e是T中除根之外的其他结点，则返回其双亲的数据信息
  代码如下：

//时间复杂度为O(n)
ElemType Parent_PT(PTree T,ElemType e) 
{ //返回双亲顺序表T中结点e的双亲的数据信息for(i=0;((i<T.num)&&T.tnode[i].data!=e);i++);if(i>=T.num)  Error("Node-e is not exist!");k=T.tnode[i].parent; // e双亲在T.tnode[i]中下标if(k==-1)  Error("Node-e has not parent!");else  return T.tnode[k].data;
}

2.孩子表示法

孩子链表
以单链表存储结点的孩子，则 n 个结点有 n 个孩子链表，其头指针采用顺序存储结构按层序存储。采用这种存储结构的树称为孩子链表

孩子链表的类型定义

#define Tree_Size  100			// 树中结点的最大个数
typedef struct CTNode 
{ int	 child;		// 孩子结点在表头数组中的下标struct CTNode* next;		// 指向下一个孩子结点
}CTNode,*ChildPtr; 
typedef struct
{ ElemType	data;		// 树中结点的数据信息ChildPtr	firstchild;	// 该结点孩子链表的头指针
}PTNode; 
typedef struct  
{ PTNode	 tnode[Tree_Size];	// 表头数组int  num;		// 树中的结点个数
}CTree; 

孩子链表的特点

• 适合求指定结点的孩子及孩子兄弟的操作
• 如果求指定结点的双亲或祖先（包括根），则需要遍历整个结构

在孩子链表中求结点孩子：
假设T中值为e的结点不多于1个：
① 如果e不存在，则给出相应信息；
② 如果e是T中某结点但无孩子，则给出相应信息；
③ 如果e是T中某结点且有孩子，则返回其第i个孩子的数据信息。

//时间复杂度为O(tn+cn)，其中tn为树T的结点个数，cn为给定结点e的孩子个数
Elemtype Children_CT(CTree T,ElemType e,int i) 
{//返回孩子链表T中结点e的第i个孩子的数据信息int j;for(j=0;((j<T.num)&&T.tnode[j].data!=e);j++);if(j>=T.num)  Error("Node-e is not exist!");else  {p=T.tnode[j].firstchild;if(!p)  Error("Node-e has not children!");j=1;while(p&&(j<i))  {  p=p->next;  ++j;  }if(!p||(j>i))  Error(" Parameter Error!");else  {k=p->child;		// e第i个孩子在T.tnode[i]中下标return T.tnode[k].data;} }
} // Children_CT

3.双亲孩子表示法

在树的孩子链表的表头结点结构中增加一个双亲域，即将树的双亲顺序表与树的孩子链表结合起来。

采用这种存储结构的树称为双亲孩子链表

结构如下：

图示如图：

双亲孩子链表的类型定义

#define Tree_Size  100			// 树中结点的最大个数
typedef struct CTNode 
{ int  child;		// 孩子结点在表头数组中的下标struct CTNode  *next;		// 指向下一个孩子结点
}CTNode,*ChildPtr; 
typedef struct PCTNode  
{ ElemType  data;		// 树中结点的数据信息int	 parent;		// 该结点双亲在表头数组中的下标childPtr   firstchild;	// 该结点孩子链表的头指针
}PCTNode; 
typedef struct  
{ PCTNode	  tnode[Tree_Size];	// 表头数组int	  num;		// 树中的结点个数
} PCTree; 

• 这种存储结构不仅表示了树中结点的双亲信息，也表示了孩子信息及孩子兄弟及孩子兄弟结点之间的关系
• 适合求指定结点的双亲或祖先的操作，也适合求指定结点的孩子的操作。

4.孩子兄弟表示法

• 链表中的结点是同构的，每个结点除了数据域外，还设置了两个指针域，分别指向该结点的第一个孩子和下一个兄弟
• 采用这种存储结构的树称为孩子兄弟链表，又称为二叉链表

结构体形式如下：
（左第一个孩子，右兄弟）


二叉链表的类型定义

typedef struct CSNode  
{ElemType	 data; // 存储树中结点的数据信息struct CSNode  *firstchild;	// 指向该结点的第一个孩子结点struct CSNode  *rightsib;	// 指向该结点的下一个兄弟结点
}CSNode; 
typedef CSNode *CSTree;

• 利用该存储结构易于实现查找结点孩子等操作
• 如果要查找某结点双亲，则需遍历整个结构

四.树的性质

• 树中的结点数等于所有结点的度数加一

• 度为m的树中第i层上至多有m^(i-1)个结点,此时应满足i>=1
  补充：若一棵m次树的所有叶子结点在同一层，除该层外其余每一层都是满的，这样的树称为满二叉树
  满m次树是所有相同高度的m次树中结点总数最多的树

• 高度为h的m次树至多有((m^h)-1)/(m-1)个结点
  

【例】 若一棵三次树中度为3的结点为2个，度为2的结点为1个，度为1的结点为2个，则该三次树中总的结点个数和度为0的结点个数分别是多少？

解：设该三次树中总结点个数、度为0的结点个数、度为1的结点个数、度为2的结点个数和度为3的结点个数分别为n、n0、n1、n2和n3。显然，每个度为i的结点在所有结点的度数之和中贡献i个度。依题意有：n1=2，n2=1，n3=2。由树的性质1可知
　　n=所有结点的度数之和+1
　　=0×n0+1×n1+2×n2+3×n3+1=1×2+2×1+3×2+1=11
　　又因为n=n0+n1+n2+n3
　　即：n0=n-n1-n2-n3=11-2-1-2=6
　　所以该三次树中总的结点个数和度为0的结点个数分别是11和6。

五.二叉树

基本概念与定义

二叉树是 n（n≥0）个结点的有限集合。
当 n=0 时，称为空二叉树；
任意一棵非空二叉树满足以下两个条件：

• 有且仅有一个特定的称为根的结点；
• 当 n＞1 时，除根结点外的其余结点最多被分成两个互不相交的有限集合，其中每个集合又是一棵二叉树，并称为这个根结点的左子树和右子树

二叉树是有序的，其次序不能任意颠倒，即使树中某个结点只有一棵子树也要区分它是左子树还是右子树，因此二叉树和树是两种不同的树结构

二叉树的结点数可以为0，度为2的树至少有三个结点

二叉树的特殊形态——斜树

所有结点都只有左子树或者所有结点都只有右子树的二叉树称为斜树

在斜树中，每层只有一个结点，所以斜树结点个数与其深度相同

二叉树的特殊形态——满二叉树

一棵深度为k且有2^k-1个结点的二叉树称为满二叉树

二叉树的特殊形态——完全二叉树

对一棵具有n个结点的二叉树按层序遍历，若编号为i(1<=i<=n)结点与同深度满二叉树中编号为i结点在树中位置完全相同，则称之为完全二叉树

即不一定要每层的结点都满，但是要按顺序编号的时候不能缺

特点：

• 在满二叉树最下面一层，从最右边开始连续删去若干个结点后得到的是一棵完全二叉树
• 在完全二叉树中，如果某个结点没有左孩子，则它一定没有右孩子，且该结点必定是叶结点

二叉树的重要性质

• 在二叉树的第 i 层上至多有 2^(k-1) 个结点（i >= 1)
• 深度为k的二叉树至多有 2^k-1 个结点（k >= 1)
• 对于任意一棵二叉树，如果其叶结点数为n0，度为2的结点数为n2，则有关系：n0 = n2 + 1

【例】 一棵二叉树中总结点个数为200，其中单分支结点个数为19，求其叶子结点个数。

解：依题意，n=200，n1=19。又n=n0+n1+n2，
由性质1得，n2=n0-1，
所以有：n=2n0-1+n1，
即n0=(n-n1+1)/2=91。

• 具有n个结点的完全二叉树的深度为

  (括号表示取整函数）

• 对一棵具有n个结点的完全二叉树中的结点从1开始层序遍历，则对于任意的编号为i(1<=i<=n)的结点，有：
  (1) 若 i>1，则结点 i 双亲编号为 [i/2]；否则结点 i 是根，无双亲
  (2) 若 2i≤n，则结点 i 左孩子编号为 2i；否则结点 i 无左孩子，且该结点为叶子结点
  (3) 若 2i＋1≤n，则结点 i 右孩子编号为 2i+1；否则结点 i 无右孩子

【例】 一棵完全二叉树中总结点个数为200，求其叶子结点个数。
解：依题意，n=200，由于n为偶数，所以n1=1。
又n=n0+n1+n2，由性质1得，n2=n0-1，
所以有：n=2n0-1+n1，n0=(n-n1+1)/2=100。
这样的完全二叉树中叶子结点个数为100。

二叉树顺序表

定义

对于一般二叉树，增添“虚结点”，使之“转化”为一棵完全二叉树
以一组连续空间按层序存储二叉树中所有的“实结点”和“虚结点”，采用这种存储结构的二叉树称为二叉树顺序表
（虚节点的存储位置用 " 空 ")

typedef TElemType SqBiTree[MaxSize];
SqBiTree bt;// 将下标为0的位置空着，值为'#'的结点为空结点。

二叉链表

定义

链表中的结点是同构的，每个结点除了数据域 data 外，还设置了两个指针域 lchild 和 rchild，分别指向该结点的左孩子和右孩子
采用这种存储结构的二叉树称为二叉链表


类型定义

typedef struct tnode  
{ElemType data;	//二叉树中结点的数据信息struct tnode  *lchild, *rchild; // 结点左右孩子指针
} BTNode; 

补充：三叉链表

类型定义

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

二叉树基本算法实现

创建二叉树

步骤如下：
创建二叉树A(B(D,E(G,H)),C(,F(I)))
其中只有4类字符，各类字符的处理方式如下：

• 若ch=’(’：
  表示前面刚创建的p结点存在着孩子结点，需将其进栈，以便建立它和其孩子结点的关系（如果一个结点刚创建完毕，其后一个字符不是’(’，表示该结点是叶子结点，不需要进栈）。然后开始处理该结点的左孩子，因此置k=1；
• 若ch=’)’：
  表示以栈顶结点为根结点的子树创建完毕，将其退栈；
• 若ch=’,’：
  表示开始处理栈顶结点的右孩子结点，置k=2；
• 其他情况：
  只能是单个字符，表示要创建一个新结点p，根据k值建立p结点与栈顶结点之间的联系，当k=1时，表示p结点作为栈顶结点的左孩子结点，当k=2时，表示p结点作为栈顶结点的右孩子结点
  代码如下：

void CreateBTree(BTNode * &bt,char *str)
{　 BTNode *St[MaxSize],*p=NULL;int top=-1,k,j=0;char ch;bt=NULL;		//建立的二叉树初始时为空ch=str[j];while (ch!='\0')	//str未扫描完时循环{	 switch(ch){ case '(':top++;St[top]=p;k=1; break;//为左孩子结点case ')':top--;break;case ',':k=2; break;			//为右孩子结点default:p=(BTNode *)malloc(sizeof(BTNode));p->data = ch;p->lchild = p->rchild=NULL;if (bt==NULL)	//*p为二叉树的根结点bt=p;else	//已建立二叉树根结点{     switch(k) {case 1:St[top]->lchild=p;break;case 2:St[top]->rchild=p;break;}}}j++;　ch=str[j]; }
}

销毁二叉树

当bt=NULL时 ：
f(bt) = 不做任何事情

其他情况时：
f(bt) = f(bt->lchild);
f(bt->rchild);
free(bt);

void DestroyBTree(BTNode *&bt)
{　  if (bt!=NULL){	DestroyBTree(bt->lchild);DestroyBTree(bt->rchild);free(bt);}
}

求二叉树高度算法

若bt=NULL:
f(bt)=0
其他情况:
f(bt)=max{f(bt->lchild),f(bt->rchild)}+1

代码如下：

int BTHeight(BTNode *bt) 
{   int lchilddep,rchilddep;if (bt==NULL) return(0); 		//空树的高度为0else{	lchilddep=BTHeight(bt->lchild);	//求左子树的高度为lchilddeprchilddep=BTHeight(bt->rchild);	//求右子树的高度为rchilddepreturn (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1);}
}

求二叉树结点个数算法

当bt=NULL：
f(bt)=0
其他情况:
f(bt)=f(bt->lchild)+f(bt->rchild)+1

代码如下：

int NodeCount(BTNode *bt)	//求二叉树bt的结点个数
{　   int num1,num2;if (bt==NULL)			//为空树时返回0return 0;else{	num1=NodeCount(bt->lchild);	//求左子树结点个数num2=NodeCount(bt->rchild);	//求右子树结点个数return (num1+num2+1);		//返回和加上1}
}

求二叉树叶子结点个数算法

当bt=NULL：
f(bt)=0
当*bt为叶子结点：
f(bt)=1
其他情况:
f(bt)=f(bt->lchild)+f(bt->rchild)

int LeafCount(BTNode *bt) //求二叉树bt的叶子结点个数
{       int num1,num2;if (bt==NULL)		//空树返回0return 0;else if (bt->lchild==NULL && bt->rchild==NULL) return 1;		//为叶子结点时返回1else{	num1=LeafCount(bt->lchild);	//求左子树叶子结点个数num2=LeafCount(bt->rchild); 	//求右子树叶子结点个数return (num1+num2);		//返回和}
}	

以括号表示法输出二叉树运算算法

对于非空二叉树bt：

• 先输出其元素值
• 当存在左孩子结点或右孩子结点时，输出一个“(”符号
• 递归处理左子树，输出一个“,”符号
• 递归处理右子树，最后输出一个“)”符号

void DispBTree(BTNode *bt) 
{　  if (bt!=NULL){	printf("%c",bt->data);if (bt->lchild!=NULL || bt->rchild!=NULL){	printf("(");		//有子树时输出'('DispBTree(bt->lchild);	//递归处理左子树if (bt->rchild!=NULL)	//有右子树时输出','printf(",");DispBTree(bt->rchild);	//递归处理右子树printf(")");	//右子树输出完毕，再输出一个')'}　　}
}

二叉树的遍历

先序遍历

若二叉树非空，则：
① 访问根结点；
② 先序遍历左子树；
③ 先序遍历右子树。
代码如下：

void PreOrder(BTNode *bt)
{　  if (bt!=NULL){	printf("%c ",bt->data);PreOrder(bt->lchild);PreOrder(bt->rchild);}
}

中序遍历

若二叉树非空，则：
① 中序遍历左子树；
② 访问根结点；
③ 中序遍历右子树。

void InOrder(BTNode *bt)
{      if (bt!=NULL){	InOrder(bt->lchild);printf("%c ",bt->data);InOrder(bt->rchild);}
}

后序遍历

若二叉树非空，则：
① 后序遍历左子树；
② 后序遍历右子树；
③ 访问根结点。

void PostOrder(BTNode *bt)
{　  if (bt!=NULL){	PostOrder(bt->lchild);PostOrder(bt->rchild);printf("%c ",bt->data);}
}

层序遍历

层次遍历是从根结点出发，按照从上向下，同一层从左向右的次序访问所有的结点。
在层次遍历算法中采用一个循环队列来实现。

• 实现过程：
  先将根结点进队，在队不空时循环。
  从队列中出队一个结点*p，访问它；
  若它有左孩子结点，将左孩子结点进队；
  若它有右孩子结点，将右孩子结点进队。
  如此操作直到队空为止。
  
  总结：
  三种算法的访问路径是相同的，只是访问结点的时机不同
  
  时间效率:O(n) //每个结点只访问一次
  空间效率:O(n) //栈占用的最大辅助空间

重要结论：
若二叉树中各结点的值均不相同，则：

• 由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，
• 由前序序列和后序序列却不一定能唯一地确定一棵二叉树。

二叉树的构造

给定某些遍历序列，反过来唯一地确定该二叉树的形态，这个过程称为二叉树的构造

若二叉树的先序遍历和中序遍历顺序一致，则该树为右单支树

• 由先序遍历和中序遍历可以唯一确定一棵二叉树：
  
• 由中序遍历和后序遍历可以唯一确定一棵二叉树：
  
• 由层次遍历序列和中序遍历序列可以唯一确定一棵二叉树：

层次遍历序列的第一个结点是二叉树的根结点，确定根结点后，到二叉树的中序遍历序列中找到该结点，这个结点将二叉树分为左子树、根和右子树三部分。
左子树中所有结点在层次遍历序列中出现的次序对应左子树的层次遍历序列，右子树中所有结点在层次遍历序列中出现的次序对应右子树的层次遍历序列，再采用同样的方式构造左、右子树，从而构造出整棵二叉树。

树和森林与二叉树的转换

树转换为二叉树

• 加线：在各兄弟结点间加一个连线，将其隐含的兄弟关系以“父-右子”关系表现出来
• 抹线：对于任何节点结点，除了最左边孩子外，抹掉该结点与其他孩子间的 “父-子”关系
• 调整：以树根作为二叉树根，将其与其最左孩子间“父-子”关系改为“父-左子”关系，且将各节点按二叉树层次排列

经过该方法转换后的二叉树是唯一的，且具有以下特点：
1.此二叉树根结点只有左子树，无右子树
2.转换生成的二叉树中各结点左孩子是它在树中最左孩子，右孩子是它在树中下一个兄弟

二叉树转换为树

• 加线：在各结点双亲与该结点右链上每个结点间加一连线，以“父-子”关系显示表示出来
• 
• 抹线：抹掉二叉树中所有的双亲结点与其右孩子之间的“父-右子”关系
• 
• 调整：以二叉树根节点作为树根结点，将各结点按照树的层次排列，形成树的结构

一棵没有右子树的二叉树经过该方法还原的树是为唯一的。

树遍历与二叉树遍历的对应关系

• 树的先序遍历对应二叉树的先序遍历
• 树的后序遍历对应二叉树的中序遍历
• 树的层序遍历不对应二叉树任何遍历

森林转换为二叉树

• 将森林中的每一棵子树按上述规则转换为二叉树
• 
• 连线：从第二棵二叉树开始，依次把后一棵二叉树的根节点作为前一棵二叉树根节点的右孩子
• 调整：以森林中第一棵树作为二叉树根，第一棵树子树森林转换后作为二叉树左子树，将森林中删去第一棵树后，其余树构成的森林转换后作为二叉树右子树，且将各结点按照二叉树的层次排列，形成二叉树的结构

经过该方法转换后对应的二叉树是唯一的，并具有以下特点：
● 二叉树根有左子树，也有右子树；
● 转换生成的二叉树根的左子树是原来森林中的第一棵子树，而右子树是其余树的构成。

二叉树还原为森林

• 抹线：抹掉二叉树根结点右链上所有结点间的“父-右子”关系，分成若干个以右链上的结点为根节点的子二叉树
• 转换和排列：将分好的二叉树按照上述规则还原为树，并排成一排，形成森林结构

一棵具有左子树和右子树的二叉树经过这种方法还原的森林是唯一的

森林遍历与二叉树遍历的对应关系

森林先序遍历定义：
如果森林为空，则空操作返回；否则：
① 访问森林中第一棵树的根结点；
② 先序遍历第一棵树中根结点的子树森林；
③ 先序遍历除去第一棵树之后剩余的树构成的森林

• 森林的先序遍历对应二叉树的先序遍历

森林中序遍历定义：
如果森林为空，则空操作返回；否则：
① 中序遍历第一棵树中根结点的子树森林；
② 访问森林中第一棵树的根结点；
③ 中序遍历除去第一棵树之后剩余的树构成的森林。

• 森林的中序遍历对应二叉树的中序遍历。

哈夫曼树

哈夫曼树是 n 个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树，有着非常广泛的应用。

路径：从树中一个结点到另一个结点之间的分支
路径长度：路径上的分支数目
树的路径长度：从树根到每一个结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短
结点的权：在一些应用中，赋予树中结点一个有某种意义的实数
结点的带权路径长度：结点到树根之间路径长度与结点上权乘积
树的带权路径长度：树中所有叶子结点的带权路径长度之和，也称为树的代价

如：

结点a到g的路径
路径上的分支数目为3
树的路径长度为01+12+22+32 = 12
结点的权
结点d的带权路径长度为24 = 8
树的带权路径长度为（注意是叶子结点）：21+42+73+5*3 = 47

• n个带权叶子结点的二叉树中，满二叉树或完全二叉树不一定是哈夫曼树；只有当叶子权值均相同时，满二叉树或完全二叉树才是哈夫曼树
• 在哈夫曼树中，权越大的叶子离根越近
• 哈夫曼树的形态不唯一，但其 WPL 最小

哈夫曼树算法

• 根据给定的 n 个权值 w1、w2、…、wn，构造 n 棵二叉树的森林F={T1, T2, … , Tn}，其中每棵二叉树 Ti 中都只有一个带权 wi 的根结点，其左子树和右子树均为空
• 在森林 F 中选出两棵根结点权值最小的树作为左右子树构造一棵新二叉树，且置新二叉树根结点权值为其左右子树上根结点的权值之和
• 在森林 F 中删除上面选中的那两棵根结点权值最小的二叉树，同时将新得到的二叉树加入森林 F 中
• 重复第 2 步和第 3 步，直到森林 F 中只剩下一棵树为止。这棵树便是哈夫曼树

n 个叶子哈夫曼树合并 n-1 次，产生 n-1 个新结点，共包含 2n-1 个结点
在哈夫曼树中没有度数为 1 的分支结点

哈夫曼树顺序表的定义

以一组连续空间存储哈夫曼树结点，每个结点中包含一个权值域 weight 存储结点权值，三个指示器 parent、lchild 和 rchild 分别指示其双亲和左右孩子在数组中位置
采用这种存储结构的哈夫曼树称为哈夫曼树顺序表


类型定义代码如下：

typedef struct  { int  weight;// 结点权值；若为实数，则转换为整数int  parent, lchild, rchild;	// 双亲及左右孩子在数组中的下标
} HTNode;
typedef HTNode *HuffmanTree;

构造哈夫曼树

假设：数组的0号单元不用，从1单元开始使用，共n+n-1=2n-1个存储空间

设哈夫曼树有n个叶子结点，哈夫曼树顺序表为HT。

① 初始化：首先动态申请2n个单元，然后循环2n-1次，从1单元开始，依次将1至2n-1所有单元的双亲、左孩子、右孩子的下标初始化为0；循环n次输入前n个单元中叶子结点的权值。

② 创建树：循环n-1次，通过n-1次的选择、删除与合并来创建哈夫曼树。选择是从森林中选择双亲为0且权值最小的两个根结点，删除是指将结点的双亲改为非0，合并即为将两个结点的权值和作为一个新结点的权值依次存入数组的第n+1之后的单元中，同时记录这个新结点左孩子下标和右孩子下标

代码如下：

该算法的执行时间依赖于初始化、输入权、合并树三个操作，其中：
① 初始化操作的时间依赖于哈夫曼树的结点个数2n-1，其时间复杂度为O(n)；
② 输入权操作的时间依赖于哈夫曼树叶子个数n，其时间复杂度为O(n)；
③ 合并树操作的时间依赖于构造哈夫曼树非叶子的个数n-1，由于构造一个非叶子的时间复杂度为O(i)（n≤i≤2n-1），因此其时间复杂度为O(n2)。
因此算法5.10的时间复杂度为O(n2)
void CreateHuffmanTree(HuffmanTree &HT,int n) 
{// 构造并返回n个叶子的哈夫曼树HTif(n<=1)  return;m=2*n–1;HT=new HTNode[m+1];		// 初始化：创建大小为m的HTfor(i=1;i<=m;i++) {			// 输入权：输入叶子权值HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;    }for(i=1;i<=n;i++) 			// 输入权：输入叶子权值cin>>HT[i].weight;   for(i=n+1;i<=m;++i) {	// 通过n-1次选择、删除、合并树：构造HTSelect(HT,i-1,s1,s2);	// 在HT[0..i-1]中选择两个最小权值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;}
} // CreateHuffmanTree

哈夫曼编码

• 数据压缩过程称为编码，即将文件中的每个字符均转换为一个唯一的二进制位串
• 数据还原过程称为解码，即将二进制位串转换为对应的字符

等长编码与变长编码
等长编码：将给定大小为 n 的字符集 C 中的每个字符设置同样的码长，即

向上取整，如

变长编码：将给定大小为 n 的字符集 C 中频度高的字符编码设置较短，频度低的字符编码设置较长

前缀编码：对字符集进行编码时，要求字符集中任一字符的编码都不是其他字符编码的前缀。
等长编码是一个前缀编码
最优前缀编码：平均码长或文件总长最小的前缀编码。最优前缀编码对文件的压缩效果也最佳

哈夫曼编码的定义：

用字符 ci 作为叶子，wi 做为叶子 ci 的权，构造一棵哈夫曼树，并将树中左分支和右分支分别标记为 0 和
1；将从根到叶子路径分支上的二进制组成字符串作为该叶子所表示字符的编码，称为哈夫曼编码。哈夫曼编码就是最优前缀编码

哈夫曼编码的存储表示：
因为各字符的编码长度不等，所以应该按照编码的实际长度动态分配空间。由此给出哈夫曼编码表的类型定义。

typedef char **HuffmanCode;	// 动态分配数组存储哈夫曼编码表

在给定字符集的哈夫曼树HT生成之后，依次以叶子HT[i]（0≤i≤n-1）为出发点，向上回溯至根为止。向上回溯时，走左分支则生成代码0，走右分支则生成代码1。
① 由于生成的编码与要求的编码反序，因此将生成的代码先从后往前依次存放在一个临时数组cd中，并附设一个指针start指示编码在cd中的起始位置（start初始时指示cd的结束位置）；
② 当某个字符编码完成时，再从cd的start处将编码复制到存储空间。
代码如下：

//该算法的执行时间依赖于对n个字符构造其哈夫曼编码。
//求解一个字符哈夫曼编码的时间是由叶子为出发点，向上回溯至根为止，最长路径长度为n-1，其时间复杂度为O(n)；
因此算法的时间复杂度为O(n2)
void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)  
{// 从叶子到根逆向求每个字符的哈夫曼编码，存储在哈夫曼编码HCHC=new char*[n+1];	 // 分配n个字符编码的头指针数组cd=new char[n]; // 分配临时存放每个字符编码动态数组空间cd[n-1]='\0';			// 置编码结束符for(i=1;i<=n;++i)  {	// 逐个字符求哈夫曼编码start=n–1;	// 指向最后，设置编码结束符位置初值c=i;f=HT[i].parent    // f指向结点c的双亲结点while(f！=0)  {	// 从叶子结点开始向上回溯到树根为止--start;        //回溯一次start向前指一个位置    if(HT[f].lchild==c) cd[start]='0'; //结点c是f的左孩子，则生成代码0else cd[start]='1';  //结点c是f的右孩子，生成代码1c=f; f=HT[f].parent; //继续向上回溯      }HC[i]=new char[n-start]; // 为第i个字符编码分配空间strcpy(HC[i],&cd[start]);	// 将求得的编码从临时空间cd复制到HC当前行   }delete cd;			// 释放工作空间
} // HuffmanCoding