data-structure-huffman树及其编码

二叉树的确定：

举例：如果我们知道了先序序列abdecfgh和中序序列dbeacgfh，求确定这个二叉树的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
BTNode *createBT(char pre[],char in[],int L1,int R1,int L2,int R2) 
{
	if(L1>R1)
		return NULL;  //递归出口
	BTNode *s=(BTNode *)malloc(sizeof(BTNode)); 
	s->lChild=s->rChild=NULL;
	s->data=pre[L1];  //先序序列的第一个结点是根结点
	int i;  //找出根结点在中序序列中的位置
	for(i=L2;i<=R2;++i)
		if(in[i]==pre[L1])
			break;
	s->lChild=createBT(pre,in,L1+1，L1+i-L2,L2,i-1); 
	s->rChild=createBT(pre,in,L1+i-L2+1,R1,i+1,R2);
	return s;

}

其中pre[]是先序序列，in[]是中序序列，L1,R1是先序序列的范围，L2,R2是中序序列的范围
这里就使用了一个递归，分别处理根结点下的左右子树，子树下的左右子树,如此递归下去。
其中12和13行的理由见下面：

1
2
3
4
5
6
7
8
9
10
11
12
pre:
————————————————————————————————————————————————————————————————————
   a   |   b   |   d   |   e   |   c   |   f   |   g   |   h   |
————————————————————————————————————————————————————————————————————
  L1     L1+1           L1+i-L2                           R1

in：
————————————————————————————————————————————————————————————————————
   d   |   b   |   e   |   a   |   c   |   g   |   f   |   h   |
————————————————————————————————————————————————————————————————————
  L2               i-1     i                              R2

举例：如果我们知道了中序遍历序列debghfca和后序遍历序列dbeacgfh，请确定二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
BTNode *createBT2(char post[],char in[],int L1,int R1,int L2,int R2) 
{
	if(L1>R1)
		return NULL;  //递归出口
	BTNode *s=(BTNode *)malloc(sizeof(BTNode)); 
	s->lChild=s->rChild=NULL;
	s->data=post[R1];  //后序序列的最后一个结点是根结点
	int i;  //找出根结点在中序序列中的位置
	for(i=L2;i<=R2;++i)
		if(in[i]==post[R1])
			break;
	s->lChild=createBT2(post,in,L1，L1+i-L2-1,L2,i-1); 
	s->rChild=createBT2(post,in,L1+i-L2,R1-1,i+1,R2);
	return s;
}

层次遍历序列和中序遍历序列确定二叉树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int search(char arr[],char key,int L,int R)  //查找函数，传入一个数组arr，key是要查找的值,L,R是范围
{
	int idx;  //下标
	for(idx=L;idx<=R;++idx)
		if(arr[idx]==key)
			return idx;  //找到这个值就返回下标，找不到就返回-1
	return -1;
}

void getSubLevel(char subLevel[],char level[],char in[],int n,int L,int R) //
{
	int k=0;
	for(int i=0;i<n;++i)
		if(search(in,level[i],L,R)!=-1)
			subLevel[k++]=level[i];
}

BTNode *CreateBT3(char level[],char in[],int n,int L,int R)
{
	if(L>R)
		return NULL;
	BTNode *s=(BTNode *)malloc(sizeof(BTNode));
	s->lChild=s->rChild=NULL;
	s->data=level[0];

	int i=search(in,level[0],L,R); //要在中序遍历序列in中查找level[0]这个结点的位置，在范围L,R中
	int LN=i-L;char LLevel[LN];  //LN,RN是数组长度
	int RN=R-i;char RLevel[RN];

	getSubLevel(LLevel,level,in,n,L,i-1);
	getSubLevel(RLevel,level,in,n,i+1,R);

	s->lChild=createBT3(LLevel,in,LN,L,i-1);  //递归处理
	s->rChild=createBT3(RLevel,in,Rn,i+1,R);

	return s;
}

在先序和中序序列来确定儿二叉树的情况时，知道了根结点之后，就可以在中序序列中，划分出左右子树是什么，因为他们是连续的，而在层次遍历中，他们是分散开来的，所以就有了getsubLevel函数，去查找他们，然后放到LLevel和RLevel数组中。这个函数具体是怎么做的呢，如图：


首先i将in数组（中序遍历序列）分成了左右不同的两个部分，分别是左右子树，下面是左右部分的元素在level数组中的分布情况，互相交错。我们是这样做的：在in数组中的L-i-1范围，用关键字t在level中扫描，看有和在数组in中L到i-1相同的值，有就把他们存到LLevel中。

getsublevel中sublevel是存储结果的数组，n是代表level的长度，L,R是要取的元素的范围。k是辅助从sublevel中插入元素。