一、Tree Traversals Again

二、完全二叉搜索树

什么是二叉搜索树？
左子树<根结点<右子树。

什么是完全二叉树？

完美二叉树的子部分

树的表示方法？
链表、数组（不涉及指针操作，但可能空间浪费比较严重）

题目：给定一串数列，将它以完全二叉搜索树的层序遍历方式输出。

核心算法：
 

void solve (int ALeft , int ARight , int TRoot)
{
    n = ARight - ALeft + 1;
    if (n==0)  return;
    L = GetLeftLength(n); //得到结点树为n的树其左子树结点的个数
    T[TRoot] = A[Aleft+L];
    LeftTRoot = TRoot*2+1;
    RightTRoot = LeftTRoot+1;
    solve(ALeft,ALeft+L-1,LeftTRoot);
    solve(ALeft+L+1,ARight,RightTRoot);

}

一个排序算法

计算左子树的规模

 三、Huffman Codes（最优编码）

最优编码不一定要通过哈夫曼算法得到！！！

哈夫曼编码的特点

1、最优编码——最长度（WPL）最小

2、无歧义编码——前缀码：数据仅存在于叶子结点

3、没有度为1的结点——满足1、2则必然有3.

哈夫曼树的构造：每次把权值最小的两棵二叉树合并

MinHeap H = CreateHeap（N）;创建一个空的、容量为N的最小堆

H = ReadData（N);  将f[]读入H—>Data[]中

HuffmanTree T = Huffman (H);  //建立Huffman树

int CodeLen = WPL( T , 0);


int WPL(HuffmanTree T , int Depth)
{    if( !T->Left && !T->Right)
        return (Depth * T->Weight)；

    else //负责T一定有两个孩子
        return (WPL(T->Left ， Depth-1)+WPL(T->Right ， Depth));


}

四、最短路径问题

最短问题的抽象：

在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径。

（一）无权图的单源最短路径算法

void Unweighted( Vertex S)

{        Enqueue( S,Q);

        while( !IsEmpty(Q)){
            V = Dequeue(Q);
            for(V的每一个邻接点W){
                if( dist[W] == -1){
                    dist[W] = dist[V] + 1;
                    path[W] = v;
                    Enqueue(W , Q);
                }
            }
        }
}

(二)有权图的单源最短路径

Dijkstra算法

 

 （三）多源最短路算法

方法一：直接将单源最短路算法调用|V|遍，T = O(|V|^3+|E|*|V|）——对于稀疏图效果好。

方法二：Floyd算法   T = O(|V|^3)——对于稠密图效果好点

哈夫曼编码

描述：哈夫曼编码是可变字长编码（VLC）的一种，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字。
贪心策略：把编码映射成二叉树，把频率高的字符分配给靠近根节点的叶节点，把频率低的字符放置在远离根节点的叶节点。
自底向上构造二叉编码树，由森林不断合并得到一棵二叉树。
思路分析：为了便于找到频次最低的字符，哈夫曼算法建立一个以f为键值的优先队列Q，假设编码字符集中每一字符c的频率是f( c ).哈夫曼编码算法以自底向上的方式构造最优编码树T。

• 一开始，每个字符构成只包含一个节点的树
• 合并频率最低的两棵树，并产生一棵新树，其频率为合并的两棵树的频率之和，并将新树插入优先队列Q中。
• 循环n-1次后，优先队列中只剩下一棵树，即最优二叉编码树。

struct cmp{
	bool operator()(connst int &x,const int &y){
		return x>y ;
	}
};//定义有限对列比较函数
double haffmanCoding(int n,int *freq){
	int i,total = 0,sumFreq = 0,jointFreq ;
	priority_queue<int,vector<int>,cmp> heap ;
	for(int i=0;i<n;i++){
		total += freq[i] ;  //频率总和
		heap.push(freq[i]) ;
	}//形成有限对列
	while(heap.size()>1){ //循环选择对列中频次最少的两个元素合并
		jointFreq = 0 ;   //合并两个节点的频率
		for(int i=0;i<2;i++){   //删除频次最少的两元素
			jointFreq += heap.top() ;
			heap.pop() ;
		}
		sumFreq += jointFreq ;     
		heap.push(jointFreq) ;   //优先队列中插入合并节点
	}
	return sumFreq/(1.0*total) ;   返回平均码长
}
//复杂度O(nlg(n))

单源最短路径

描述: 有向图G有n个顶点，给定每两个顶点的权值，权值为非负实数，如果权值为-1，表示没有边相连，默认第一个顶点为源。计算假设源可以到达任何一个顶点，从源到各顶点的最短路径长度。
特征：最短路径的子路径也是源到相应顶点的最短路径。
Dijstra算法：

贪心策略：选择集合V-S中受限路径长度最短的顶点，并把相应顶点加入到S中，相应地最短路径树T叶增加一条边。

代码：

#define INF 0x3f3f3f3f //预定义的充分大的数
#define MaxV 100
int preV[MaxV];  //最短路径树中的前驱节点信息表
int visited[MaxV];  //结点是否加入S的标记表，0是为加入，1是加入
void Dijkstra(int linkMatrix[][MaxV],int lowLR[MaxV],int numV,int beginV){
	int i,j,min,newCost ;
	memset(visited,0,sizeof(visited)) ;   //初始化，所有结点为加入
	//开始结点beginV加入S
	visited[beginV] = 1 ;
	for(int i=0;i<numV;i++){
		lowLR[i] = linkMatrix[beginV][i] ;
		preV[i] = beginV ;
	}
	lowLR[beginV] = 0 ;
	preV[beginV] = -1 ;  //树根的标记
	int selectV = beginV ;
	for(int i=1;i<numV;i++){
		for(int j=0;j<numV;j++){
			newCost = lowLR[selectV]+linkMatrix[selectV][j] ;
			if(visited[j]==0&&newCost<lowLR[j]){
				lowLR[j] = newCost ;
				preV[j] = selectV ;
			}
		}
		min = INF ;
		for(int j=0;j<numVlj++){
			if(visited[j]==0&&lowLR[j]<min){
				min = lowLR[j] ;
				selectV = j ;
			}
		}
		visited[selectV] = 1 ;  //更新被选中顶点的状态
	}
}

最小生成树MST

最小生成树性质

• 生成树有V个顶点，V-1条边
• 生成树中增加一条边则会得到一个回路，回路中删除任何一条边又得到一棵树
• 设G=(V,E)是连通带权图，U是V的真子集。如果（u,v）属于E，其中u属于U，v属于（V-U），称之为跨边，且在所有这样的边中，(u,v)的权C(u,v)最小，那么一定存在G的一棵最小生成树，它包含边(u,v).
  两种求解算法
  Prim算法(加点法)：针对图中的顶点设计贪心策略，逐步添加点/边构造最小生成树
  策略是选择最小跨边。
  
  代码：

#define MaxV 1000
#define INF 0x3f3f3f3f  //预定义充分大的值
int prim(int linkMatrix[][MaxV],int numV){
	int visited[MaxV] = {0} ;   //节点是否加入MIS的标记表，0表示未加入，1表示已加入
	int lowCost[MaxV],closet[MaxV] ;
	int i,k ;
	int min,costMST = 0 ;
	visited[0] = 1 ;  //顶点加入MST
	closetst[0] = -1 ;  //树根的标记
	for(int i=1;i<numV;i++){   //初始化
		lowCost[i] = linkMatrix[0][i] ;
		closest[i] = 0 ;
	} 
 	for(int i=0;i<numV;i++){
		min = INF ;
		int selectV = 0 ;
		for(int k=1;k<numV;k++){    //贪心选择最短边
			if(!visited[k]&&lowCost[k]<min){
				min = lowCost[k] ;
				selectV = k ;
			}
		}
		costMST += min ;   //更新MST树权重
		visited[selectV] = 1 ;
		for(k=1;k<numV;k++){
			if(!visited[k]&&linkMatrix[selectV][k]<lowCost[k]){
				lowCost[k] = linkMatrix[selectV][k] ;
				closest[k] = selectV ;
			}
		}
	}
	return costMST ;
}
//O(|V|^2)

Kruskal算法（加边法）：针对图中的边设计贪心策略，逐步合并分支构造最小生成树，策略是选择最短边合并两个不连通分支。
这里先补充一下并查集的概念：并查集是一种树形的数据结构，常用于处理一些不想交集合的合并和查询问题，它包含两个基本操作：查询Find和合并Union.(每个集合找一个代表)，下面部分是讲解并查集的优化方法（采用了路径压缩），更详细的解释：https://blog.csdn.net/weixin_44508223/article/details/102648509
第一步Find:路径上的每个节点都直接连接在根上。递归的访问当前节点到树根的路径，改变每一个节点的引用到根节点。

//初始化father[]数组为-1，也就是，代表树中只有一个节点
int Find(int x){
	int p = x ;
	while(father[p]>0)
		p = father[p] ;   //找到树根
	return p ;
	//将每一个节点都指向根节点
	while(father[x]!=p&&father[x]>0){
		int temp = father[x] ;
		father[x] = p ;  //指向树根
		x = temp ;
	}
	return p ;
}

第二步Union:按秩合并，即总是将更浅的树连接至更深的树上，避免增加合并数的秩。（这里的秩表示树的深度，单个元素的树的秩定义为0），当两个树的秩同为r时，它们的秩变为r+1,为了方便比较，把集合的秩的相反数存储在根节点。

void Union(int x,int y){
	int xRoot = Find(x) ;
	int yRoot = Find(y) ;
	if(xRoot==yRoot)  return ;
	if(-father[xRoot]>-father[yRoot])
		father[yRoot] = xRoot ;
	else{
		if(father[xRoot] == father[yRoot])
			father[yRoot] -= 1 ;   //相等
		father[xRoot] = yRoot ;
	}
}

Kruskal算法俗称闭环法，该算法的实现关键是在加边时避免出现环路，用并查集来实现连通分支查找和合并的相关操作。
一开始各个顶点是孤立的，然后选择边集中权值最小的边(i,j)，如果加入不产生回路，则加入，否则舍弃，直到加够n-1条边为止。

int Kruskal(node juSet[MaxV],int numV,edge degeSet[MaxE],int numE){
	qsort(edgeSet,numE,sizeof(struct edge),cmp) ;   //将边排序
	int totalCost = 0,cntE = 0,fatherX,fatherY ;
	for(int i=0;i<numE;i++){
		fatherX = Find_Set(edgeSet[i].x) ;
		fatherY = Find_Set(edgeSet[i].y) ;
		if(fatherX!=fatherY){
			Union(fatherX,fatherY) ;
			totalCost += edgeSet[i].w ;
			cntE++ ;
		}
		if(cntE == numV-1) // 完成
			return totalCost ;
	}
}
//O（elog(e)）

树中的内容：

---------------------------------------------------------------------------------------------------------------------------------

图中的内容：

 带权图的最短路径和距离：