PTA Huffman Codes 思路分析及具体实现 v1.0

本文主要是介绍PTA Huffman Codes 思路分析及具体实现 v1.0，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

PTA 7-9 Huffman Codes 思路分析及具体实现

一、前导
- 1. 写在前面
- 2. 需要掌握的知识
- 3. 题目信息
二、解题思路分析
- 1. 题意理解
- 2. 思路分析（重点）
三、具体实现
- 1. 弯路和bug
- 2. 代码框架（重点）
- - 2.1 采用的数据结构（重点）
  - 2.2 程序主体框架
  - 2.3 各分支函数（重点）
- 3. 完整编码
四、参考

一、前导

目前只做到了AC ( ╯□╰ )，代码质量惨不忍睹
21.10.13 ：对代码进行了优化

1. 写在前面

写博客的原因非常简单：好记性不如烂笔头。已经屡次被现实教育，虽然现在AC，如果下次再遇到，很可能重头开始
其次，对思路和走过的坑(遇到的bug)进行系统性梳理，有利于自己成长，AC并不是终点，而是另一个起点
和大家分享

2. 需要掌握的知识

这道题难度不小，如果对下面的知识点不熟悉，建议延后做
Huffman树：具备最小WPL；满足前缀编码；没有节点为1的子树
前缀编码：任何一个字符的编码都不是其他字符编码的前缀
堆：这里的堆不是堆栈，而是一种特殊的数据结构，堆按照优先级排序，堆顶的元素是最小的(小顶堆)或最大的(大顶堆)，可以通过数组存储，通过完全二叉树表示。
编程能力：堆、树
其他：建堆和建Huffman树代码量都挺大，有很多大神在未建树的情况下也AC啦
注意，本文介绍的是通过建Huffman树解决问题的方法，代码量还是蛮大的，如果说好处：那就是结合实际编码熟悉堆和哈夫曼树

3. 题目信息

题目来源：PTA / 拼题A
题目地址：https://pintia.cn/problem-sets/16/problems/671

二、解题思路分析

1. 题意理解

输入数据

//如下是输入数据
3  //需要编码的字符个数
a 1 b 1 c 2 //字符及其出现的频率
1 //提交编码的人数
a 00 //提交的编码
b 01 //提交的编码
c 1 //提交的编码

输出数据
符合要求打印Yes，不符合输出No：print in each line either “Yes” if the student’s submission is correct, or “No” if not
题意
对学生提交的编码进行判定，若wpl最小且编码正确(满足前缀编码的要求)，打印 Yes，否则打印 No

2. 思路分析（重点）

依据题意，围绕两点进行编码即可满足题目的判定要求：（1）提交的编码WPL(Weighted Path Length of Tree)是最小的（2）各字符编码满足前缀编码的要求。不需要考虑节点为1的判定条件。
思考：如果一棵树wpl最小且满足前缀码要求，它有节点为1的子树吗？
答：进行反证。
假设存在子树为1的节点，该树的WPL最小且满足前缀编码的要求。首先，子树为1的节点不能存储数据，否则会破坏前缀编码要求。其次，数据一定存储在其下方的叶节点上，若拿掉子树为1的节点（确实可拿掉），WPL会减少，这个和 WPL最小矛盾。
另外需要注意：Huffman树的WPL最小，但WPL最小的树不一定是Huffman树。只要WPL最小且满足前缀编码要求的学生答案都是正确的。
如何计算出最小WPL？如何确保编码满足前缀编码的需求？

三、具体实现

1. 弯路和bug

我一开始老想将元素(就是a 1 b 1 中的a,b )也通过结构体记录下来，最后发现完全没有必要，结构体中只存储频率即可。
为什么不用记录元素？ WPL计算和前缀编码判定都是通过频率进行的，和元素没有任何关系。而且元素的顺序前后都是一致的。
我一开始思维始终局限在堆中的元素只能是int char 等单个元素，其实堆中的元素也可以是结构体，比如：树
注意别遗漏检查编码相同的异常情况，即 a b的编码结果都是 00
检查完一位学生后，需要恢复默认值

2. 代码框架（重点）

代码框架是我们容易忽视的内容，我们往往喜欢最快时间开始编码。其实就像盖房子，需要先画图纸然后再施工一样。程序也需要进行概要设计(框架)，再进行详细设计(Code)。需要先想好采用的数据结构及需要的函数

2.1 采用的数据结构（重点）

使用小顶堆的目的是为了创建Huffman树，每次从堆中取出两个频率最小的Huffman树，通过这两个Huffman树建一棵二叉树，然后将新建的树再插回小顶堆中。然后重复，上述操作需要执行N-1次(共N个元素)，最后形成一棵Huffman树

typedef struct TreeNode *HuffmanTree;
struct TreeNode
{int Weight;HuffmanTree Left,Right;
};//Huffman树的结构typedef struct HeapNode *MinHeap;
struct HeapNode  
{HuffmanTree *HTree;int Size;
};//堆结构，堆由一棵棵的Huffman树组成

2.2 程序主体框架

个人认为这个习惯很重要，先完成程序的大体框架并理清思路（详设）

               程序伪码描述
int main()
{	1.创建一个空的最小堆;2.接收录入的数据并创建一棵棵Huffman树，将这一棵棵树插入创建的最小堆中3.通过最小堆创建一棵Huffman树4.通过Huffman树得到wpl5.处理学生录入的数据：（1）计算其wpl，和得到的wpl比对 （2）判定是否满足前缀码要求6.打印判断结果return 0;
}

2.3 各分支函数（重点）

MinHeap CreatMinHeap(int n); //创建一个空堆
void InsertMinHeap(MinHeap H,HuffmanTree HTree ); //将元素插入到最小堆中
HuffmanTree DeleteMin(MinHeap H);
HuffmanTree Huffman(MinHeap H);
int WPL(HuffmanTree HTree,int depth); 
bool Judge(HuffmanTree HTree,bool value,bool end);

CreatMinHeap() ：创建空堆。需要注意2点：（1）堆里存储的是一棵棵Huffman树，通过Weight进行排序；（2）设定好哨兵，也就是数组的0号

MinHeap CreatMinHeap(int n)
{MinHeap H;H=(MinHeap)malloc(sizeof(struct HeapNode));H->Size=0;H->HTree=(HuffmanTree*)malloc(sizeof(struct TreeNode)*(n+1)); //n棵Huffman树 + 1个哨兵 HuffmanTree tmp; //tmp是哨兵，其Weight是最小值tmp=(HuffmanTree)malloc(sizeof(struct TreeNode));tmp->Left=NULL;tmp->Right=NULL;tmp->Weight=-1;H->HTree[Guard]=tmp;return H;
}

InsertMinHeap()：将一棵棵Huffman树插入到堆中，形成小顶堆。栗子：对于输入 a 1 b 1 c 2，可以把频率 1 1 2 看成三棵单节点的Huffman树

void InsertMinHeap(MinHeap H,HuffmanTree HTree)  
{int i = ++H->Size; for(; HTree->Weight < H->HTree[i/2]->Weight ; i=i/2 ){H->HTree[i]=H->HTree[i/2];  //堆中的元素是一棵棵的树，按频率进行排列。堆可以看作是一棵完全二叉树 }H->HTree[i]=HTree;return;
}

DeleteMin()：目的是为了取出最小频率的子树，被Huffman()函数调用。Delete本身很简单，取出顶部的元素即可(数组序号是1)，编码难点是对剩余的元素进行调整，以便取出元素后剩余的元素仍然是小顶堆

HuffmanTree DeleteMin(MinHeap H)
{HuffmanTree HTree;HTree=H->HTree[Top]; H->HTree[Top]=H->HTree[H->Size--];int father,child; HuffmanTree tmp;father=Top; child=2*father; while(child <= H->Size)  //说明有儿子 {if( child+1 <= H->Size && H->HTree[child+1]->Weight < H->HTree[child]->Weight )child++;if(H->HTree[child]->Weight < H->HTree[father]->Weight){tmp=H->HTree[father];H->HTree[father]=H->HTree[child];H->HTree[child]=tmp;father=child;child=2*father;}elsebreak;	}return HTree;
}

Huffman()：根据输入创建一棵Huffman树，为后续计算WPL打基础。创建Huffman树完全模拟Huffman树的建树过程，每次从集合中取出两棵频率最低的树，合并后放回原集合，然后重复N-1次(小顶堆共N个元素)

HuffmanTree Huffman(MinHeap H)
{int i; HuffmanTree T; int loop = H->Size;for(i=1; i<loop; i++) //bug:H->Size一直再变啊，需要固定住 {T=(HuffmanTree)malloc(sizeof(struct TreeNode)); T->Left=DeleteMin(H); T->Right=DeleteMin(H);T->Weight=T->Left->Weight + T->Right->Weight;InsertMinHeap(H,T); }T=DeleteMin(H);return T;
}

WPL()：计算自己创建的Huffman树的wpl值，用于和学生提交的进行比对。通过递归实现比较容易

int WPL(HuffmanTree T,int depth)
{if(!T->Left && !T->Right)return (T->Weight*depth);else //由于是二叉树，一定有两个子树 {return (WPL(T->Left,depth+1) + WPL(T->Right,depth+1)); //depth++就是错的 why？ }	
}

Judge(string a,string b)：判定学生的编码是否满足前缀编码（不存在二义性）
21.10.13：编码不存在二义性，就是不能出现如下情况：001 0011 前者被后者包含或 011 01 后者被前者包含

bool Judge(string a, string b)
{for (int i = 0; i < a.length() && i < b.length(); i++)if (a[i] != b[i])return true;return false;
}

以前的思路（不可取）：
思路是根据学生的录入创建Huffman树，然后在建树的过程中进行前缀码检查，模拟人工检查。我的Judge()实现的很不好，可以用惨不忍睹形容，这里就不列出了，后面我会找时间改进。
Judge函数的思路：模拟手动检查，如果遇到0，新建一棵左子树或向左子树下移一格；如果遇到1，新建一棵右子树或向右子树下移一格。特殊的，编码的最后一位：判定其下方是否有左右子树；若有，左右子树 Weight值为 1 时违反前缀码。注意别遗漏检查编码相同的情况，即 a b的编码结果都是 00

3. 完整编码

21.10.13的AC代码：靠之前的自己续命 + 帮助以前的自己，这道题是一场苦战

#include <iostream>
using namespace std;typedef struct TreeNode* HuffmanTree;
typedef struct Heap *MinHeap; //将MinHeap切换为*MinHeap，使用指针更灵活，将其作为参数传入，效果类似实参：可以真正改变（这个理解不严谨）struct Heap
{HuffmanTree *HTree; //存放哈夫曼树的数组int Size;//不统计哨兵
};struct TreeNode
{	//A 1 B 1 C 1 D 3 E 3 F 6 G 6int Freq;//为什么不记录A B C 只记录频率1 1 1? 因为根据哈夫曼树的特点，待计算WPL的结点都位于叶结点（知道出现频率就可以了）HuffmanTree Left;HuffmanTree Right;
};MinHeap CreateEmptyHeap(int N);
void InsertHeap(MinHeap MHeap, HuffmanTree HTree);HuffmanTree DeleteHeap(MinHeap MHeap); //从小顶堆中取出最小的Huffman树
HuffmanTree ConstructHuffman(MinHeap MHeap); //依次取出两个Huffman树，合并后插入原堆中，重复，直到Size=1;int CalcWPL(HuffmanTree Tree,int Height);
bool Judge(string a, string b);int main()
{int N;  cin >> N;MinHeap MHeap = CreateEmptyHeap(N);int* a = new int[N]; //存储所有元素出现的频率 计算WPL会用上char Symbol; int Freq;for (int i = 0; i < N; i++)//A 1 B 1 C 1 D 3 E 3 F 6 G 6{cin >> Symbol >> Freq;a[i] = Freq;HuffmanTree HTree;HTree = new struct TreeNode;HTree->Freq = Freq;HTree->Left = HTree->Right = NULL;InsertHeap(MHeap, HTree); //二叉树构建的最小堆 完毕}HuffmanTree Reference;Reference = ConstructHuffman(MHeap);int RefWPL = CalcWPL(Reference, 0);int Student; cin >> Student;string Code; string* b = new string[N];//数组b用于记录编码for (int i = 0; i < Student; i++){int StuWPL = 0;for (int i = 0; i < N; i++){cin >> Symbol >> Code;b[i] = Code;StuWPL += Code.length() * a[i];}bool Flag = true;if (RefWPL == StuWPL)//WPL一致的情况下 判定是否存在二义性{for (int i = 0; i < N && Flag; i++)for (int j = i + 1; j < N && Flag; j++)Flag = Judge(b[i], b[j]);			if (Flag)cout << "Yes" << endl;elsecout << "No" << endl;}elsecout << "No" << endl;}return 0;
}bool Judge(string a, string b)
{for (int i = 0; i < a.length() && i < b.length(); i++)if (a[i] != b[i])return true;return false;
}int CalcWPL(HuffmanTree Tree, int Height)
{if (!Tree->Left && !Tree->Right) //叶结点就是待计算的结点return Tree->Freq * Height;elsereturn CalcWPL(Tree->Left, Height + 1) + CalcWPL(Tree->Right, Height + 1);
}HuffmanTree DeleteHeap(MinHeap MHeap)
{HuffmanTree Tree = MHeap->HTree[1];//取出最小的Huffman树的index=1 , 0 is Guard//将剩余的元素再次调整为最小堆MHeap->HTree[1] = MHeap->HTree[MHeap->Size--];int Parent = 1, Child = Parent * 2;while (Child <= MHeap->Size){if ((Child + 1 <= MHeap->Size) && (MHeap->HTree[Child + 1]->Freq < MHeap->HTree[Child]->Freq))Child++;HuffmanTree Tmp;if (MHeap->HTree[Child]->Freq < MHeap->HTree[Parent]->Freq){Tmp = MHeap->HTree[Parent];MHeap->HTree[Parent] = MHeap->HTree[Child];MHeap->HTree[Child] = Tmp;Parent = Child;Child = Parent * 2;}elsebreak;}return Tree;
}HuffmanTree ConstructHuffman(MinHeap MHeap)
{int Loop = MHeap->Size - 1;HuffmanTree Tree01, Tree02,Tree;for (int i = 0; i < Loop; i++){Tree01 = DeleteHeap(MHeap);Tree02 = DeleteHeap(MHeap);Tree = new struct TreeNode;Tree->Freq = Tree01->Freq + Tree02->Freq;Tree->Left = Tree01; Tree->Right = Tree02;InsertHeap(MHeap, Tree);}return DeleteHeap(MHeap);
}void InsertHeap(MinHeap MHeap, HuffmanTree HTree)
{	int i = ++MHeap->Size; //在堆中可能的插入位置while (HTree->Freq < MHeap->HTree[i/2]->Freq) //调整为小顶堆{MHeap->HTree[i] = MHeap->HTree[i/2];i /= 2;}MHeap->HTree[i] = HTree;return ;
}MinHeap CreateEmptyHeap(int N)
{MinHeap MHeap; MHeap = new struct Heap;MHeap->Size = 0;MHeap->HTree = new HuffmanTree[N + 1]; //0是哨兵 + N个元素HuffmanTree Guard = new struct TreeNode;//哨兵Guard->Freq = -1;Guard->Left = Guard->Right = NULL;MHeap->HTree[MHeap->Size] = Guard; //哨兵不算正式元素，因此 MHeap->HTree[MHeap->Size++] = Guard 是错误的;return MHeap;
}
/*
0.数据结构：（1）通过结构体存储堆、堆由一棵棵哈夫曼树构成（2）根据Huffman树的特点，待统计WPL的结点都处于叶结点
1.构建Huffman树：（1）最小堆（由一颗颗树构成）（2）每次取出两个最小的树->处理后放回最小堆->再取出两个最小的...直到全部取出（3）取出意味着堆删除元素，插入意味堆新增元素
2.构建完毕，统计WPL
3.判定：（1）最小编码长度应该相同 （2）编码不存在二义性,即不能出现如下情况：001 0011 前者被后者包含 或 011 01 后者被前者包含
*/

之前的AC代码

#include <cstring>
#include <queue>
#include <cstdlib>
#include <iostream>
using namespace std;#define Top 1
#define Guard 0    //7   A 1 B 1 C 1 D 3 E 3 F 6 G 6
#define Max 100typedef char ElementType;   //不记录元素，只记录频率试试typedef struct TreeNode *HuffmanTree;
struct TreeNode
{int Weight;HuffmanTree Left,Right;
};typedef struct HeapNode *MinHeap;
struct HeapNode  
{HuffmanTree *HTree;int Size;
};HuffmanTree DeleteMin(MinHeap H);void InsertMinHeap(MinHeap H,HuffmanTree HTree );
MinHeap CreatMinHeap(int n);
HuffmanTree Huffman(MinHeap H);
void PrintTree(HuffmanTree T);
void PrintHeap(MinHeap H);
int WPL(HuffmanTree HTree,int depth); 
bool Judge(HuffmanTree HTree,bool value,bool end);int main()
{	int n;cin>>n;MinHeap H;H=CreatMinHeap(n);ElementType data;int freq;HuffmanTree HTree;   int a[n]; for(int i=0;i<n;i++){cin>>data>>freq;a[i]=freq;HTree=(HuffmanTree)malloc(sizeof(struct TreeNode));HTree->Weight= freq; HTree->Left=NULL; HTree->Right=NULL; //每棵树都是单节点 InsertMinHeap(H,HTree);}HTree=Huffman(H); int wpl;wpl=WPL(HTree,0);HuffmanTree  Judge_Tree , Judge_Tree_bak;Judge_Tree=(HuffmanTree)malloc(sizeof(struct TreeNode));Judge_Tree->Weight=0;Judge_Tree->Left=NULL;Judge_Tree->Right=NULL;Judge_Tree_bak=Judge_Tree;int m; // m represent student's numbercin>>m;char code[Max]; bool flag=1; int current_wpl=0; int tmp; bool end=0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){cin>>data>>code; //A 00000current_wpl=current_wpl+a[j]*strlen(code);if(flag==false) continue;for(int k=0;k<strlen(code);k++) //根据编码进行建树 {tmp=code[k]-'0';if(k== (strlen(code)-1) ) end=1;flag=Judge(Judge_Tree,tmp,end);if(tmp==0) {//cout<<"go left subtree "<<endl;Judge_Tree=Judge_Tree->Left;}else {//cout<<"go right subtree "<<endl;Judge_Tree=Judge_Tree->Right;}} //loop endJudge_Tree=Judge_Tree_bak;end=0;}Judge_Tree->Left=NULL; Judge_Tree->Right=NULL;//cout<<"current_wpl:"<<current_wpl<<endl;if(current_wpl!=wpl) flag=0;if(flag==1) cout<<"Yes"<<endl;else cout<<"No"<<endl;	flag=1;current_wpl=0; //fix bug, add this code.}//}return 0;
}bool Judge(HuffmanTree HTree,bool value,bool end)
{//bool flag==1;if(value==0 && !HTree->Left && end!=1)  //{//cout<<"value==0 && !HTree->Left && end!=1"<<endl;HuffmanTree T;T=(HuffmanTree)malloc(sizeof(struct TreeNode));T->Weight=0;T->Left=NULL;T->Right=NULL; //bug  no defalut valueHTree->Left=T;//HTree=HTree->Left;return true;}if(value==0 && !HTree->Left && end==1){//cout<<"value==0 && !HTree->Left && end==1"<<endl;HuffmanTree T;T=(HuffmanTree)malloc(sizeof(struct TreeNode));T->Weight=1;T->Left=NULL;T->Right=NULL;HTree->Left=T;//HTree=HTree->Left;	return true;	}if(value==0 && HTree->Left && end!=1){//cout<<"value==0 && HTree->Left && end!=1"<<endl;//HTree=HTree->Left;return true;}if(value==0 && HTree->Left && end==1){//cout<<"value==0 && HTree->Left && end==1 "<<endl;HuffmanTree bak;HTree=HTree->Left;if(HTree->Weight==1) return false;else HTree->Weight=1;bak=HTree;while(HTree->Left){if(HTree->Left->Weight==1){//cout<<"got it!!!"<<endl;return false;}HTree=HTree->Left;}HTree=bak;while(HTree->Right){if(HTree->Right->Weight==1){//cout<<"got it!!!"<<endl;return false;}HTree=HTree->Right;}//HTree=bak;return true;}// -------------------sepereate-------------------------------if(value==1 && !HTree->Right && end!=1)  //{//cout<<"value==1 && !HTree->Right && end!=1"<<endl;HuffmanTree T;T=(HuffmanTree)malloc(sizeof(struct TreeNode));T->Weight=0;T->Left=NULL;T->Right=NULL;HTree->Right=T;//HTree=HTree->Right;return true;}if(value==1 && !HTree->Right && end==1){//cout<<"value==1 && !HTree->Right && end==1"<<endl;HuffmanTree T;T=(HuffmanTree)malloc(sizeof(struct TreeNode));T->Weight=1;T->Left=NULL;T->Right=NULL;HTree->Right=T;//HTree=HTree->Right;return true;}if(value==1 && HTree->Right && end!=1){//HTree=HTree->Right;//cout<<"value==1 && HTree->Right && end!=1"<<endl;return true;}if(value==1 && HTree->Right && end==1){//cout<<"Here is value==1 && HTree->Right && end==1" <<endl;HuffmanTree bak;HTree=HTree->Right;if(HTree->Weight==1) return false;else HTree->Weight=1;bak=HTree;while(HTree->Right){if(HTree->Right->Weight==1){//cout<<"got it!!!"<<endl;return false;}HTree=HTree->Right;}HTree=bak;while(HTree->Left){if(HTree->Left->Weight==1){//cout<<"got it!!!"<<endl;return false;}HTree=HTree->Left;}//HTree=bak;return true;}//return true; 
}int WPL(HuffmanTree T,int depth)
{//int wpl;if(!T->Left && !T->Right)return (T->Weight*depth);else //由于是二叉树，一定有两个子树 {return (WPL(T->Left,depth+1) + WPL(T->Right,depth+1)); //depth++就是错的 why？ }//return wpl;}void PrintHeap(MinHeap H)
{for(int i=1;i<=H->Size;i++)cout<<H->HTree[i]->Weight<<endl;
} void PrintTree(HuffmanTree T)
{HuffmanTree HTree,x;HTree=T;queue<HuffmanTree> q; q.push(HTree);while(!q.empty()){x=q.front();cout<<x->Weight<<' ';q.pop();//q.push(T->Left->Weight);   //没有子树如何处理  如何自动打印 //q.push(T->Right->Weight);if(x->Left) {q.push(x->Left);}if(x->Right){q.push(x->Right);}//T=T->Left}return;
}HuffmanTree DeleteMin(MinHeap H)
{//cout<<"Here is Del Fun."<<endl;HuffmanTree HTree;HTree=H->HTree[Top]; H->HTree[Top]=H->HTree[H->Size--];int father,child; HuffmanTree tmp;father=Top; child=2*father; while(child <= H->Size)  //说明有儿子 {if( child+1 <= H->Size && H->HTree[child+1]->Weight < H->HTree[child]->Weight )child++;if(H->HTree[child]->Weight < H->HTree[father]->Weight){tmp=H->HTree[father];H->HTree[father]=H->HTree[child];H->HTree[child]=tmp;father=child;child=2*father;}elsebreak;	}//H->Frequent[H->Size--];return HTree;
}HuffmanTree Huffman(MinHeap H)
{int i; HuffmanTree T; int loop = H->Size;for(i=1; i<loop; i++) //bug:H->Size一直再变啊，需要固定住 {T=(HuffmanTree)malloc(sizeof(struct TreeNode)); T->Left=DeleteMin(H); //bug? //PrintTree(T->Left);T->Right=DeleteMin(H);//PrintTree(T->Right);T->Weight=T->Left->Weight + T->Right->Weight;InsertMinHeap(H,T);  //bug?}T=DeleteMin(H);//cout<<"Print the Final T..."<<endl;//PrintTree(T);return T;
}
void InsertMinHeap(MinHeap H,HuffmanTree HTree)  //Insert(H,T); //Insert???
{int i = ++H->Size; for(; HTree->Weight < H->HTree[i/2]->Weight ; i=i/2 ){H->HTree[i]=H->HTree[i/2];  //堆中的元素是一棵棵的树，按频率进行排列。堆 完全二叉树 }H->HTree[i]=HTree;return;
}MinHeap CreatMinHeap(int n)
{//cout<<"Here is Create Func."<<endl;MinHeap H;H=(MinHeap)malloc(sizeof(struct HeapNode));H->Size=0;H->HTree=(HuffmanTree*)malloc(sizeof(struct TreeNode)*(n+1)); //通过指针表示数组 HuffmanTree tmp;tmp=(HuffmanTree)malloc(sizeof(struct TreeNode));tmp->Left=NULL;tmp->Right=NULL;tmp->Weight=-1;H->HTree[Guard]=tmp;return H;
}