发布网友 发布时间:2022-04-27 04:44
共1个回答
热心网友 时间:2022-06-26 10:22
排序是一种十分重要的运算。所谓排序就是把一堆杂乱无章的元素按照某种次序排列起来,形成一个线性有序的序列。二叉排序树是利用二叉树的结构特点来实现对元素排序的。
一、二叉排序树的定义
二叉排序树或者是空树,或者是具有如下性质的二叉树:
1、左子树上所有结点的数据值均小于根结点的数据值;
2、右子树上所有结点的数据值均大于或等于根结点的数据值;
3、左子树、右子树本身又各是一棵二叉排序树。
由此可见,二叉排序树是一种特殊结构的二叉树。(18(10(3,15(12,15)),21(20,21(,37))))就是一棵二叉排序树。
二、二叉排序树的构造
二叉排序树的构造过程实质上就是排序的过程,它是二叉排序树作媒介,将一个任意的数据序列变成一个有序序列。二叉排序树的构造一般是采用陆续插入结点的办法逐步构成的。具体构造的思路是:
1、以待排序的数据的第一个数据构成根结点;
2、对以后的各个数据,逐个插入结点,而且规定:在插入过程的每一步,原有树结点位置不再变动,只是将新数据的结点作为一个叶子结点插入到合适的位置,使树中任何结点的数据与其左、右子树结点数据之间的关系仍然符合对二叉排序树的要求。 一、哈夫曼树的含义:哈夫曼树是一种带权路径长度最短的树。
所谓路径长度就是某个端结点到树的根结点的距离,等于该端结点的祖先数,或该结点所在层数减1,用lk表示。二叉树中每个端结点对应的一个实数称为该结点的权,用Wk表示。我们定义各端结点的权Wk与相应的路径程度lk乘积的代数和为该二叉树的带权路径长度,用WPL表示,即:
可以证明,哈夫曼树是最优二叉树。如给定权值{5,4,7,2,3},可以生成很多棵二叉树,其中的(A(B(7,5),C(4,D(3,2))))是哈夫曼树。
二、哈夫曼树的构造
1、哈夫曼算法:
(1)根据给定的n个权值{W1,W2,…,Wn}构成n棵二叉树的森林:F{T1,T2,…,Tn}。其中每棵二叉树Ti只有一个带权为Wi的根结点,其左右子树为空。
(2)在F中选取两棵结点的权值最小的树作为左右子树构成一棵新的二叉树,且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
(3)在F中删除这两棵树,同时,将新得到的二叉树加入F中。
(4)重复(2)、(3),直到F只含一棵树为止。最后的这棵树便是哈夫曼树。
2、算法描述
为了上述算法,选用数组型的链表作为存储结构,其类型设计如下:
Type tnode=RECORD
weight:real;
Lc,Rc:integer;
END;
tree=ARRAY[1..2*n-1] of tnode;
node=RECORD
weight:real;
adr:integer;
END;
A=ARRAY[1..n] of node;
下面是在这个存储结构上实现的构造哈夫曼树的算法:
Procere Huffmantree(VAR W:ARRAY[1..n]OF real;VAR TR:tree);
VAR AT:A;
BENGIN
FOR i:=1 TO n DO{实现第(1)步}
BEGIN
TR[i].weight:=W[i];{将权值放在树叶中}
TR[i].Lc:=0;
TR[i].Rc:=0;
AT[i].weight:=TR[i].weight;{用AT存放当前森林的根}
AT[i].adr:=i;
END;
num:=n;{森林中结点个数}
K:=num+1;{形成的新结点在TR数组中的位置}
WHILE (num>=2) DO {重复实现第(2)、(3)步}
BEGIN
SORTING(AT,num);{按根值大小对森林中的树进行升序排列}
TR[k].weight:=AT[1].weight+AT[2].weight;
{选择两棵结点权值最小的树构造新二叉树}
TR[k].Lc:=AT[1].adr; {左子树:权值最小的树}
TR[k].Rc:=AT[2].adr; {右子树:权值次小的树}
AT[1].weight:=TR[k].weight; {新树赋予第一}
AT[1].adr:=k; {新树结点标号}
AT[2].weight:=AT[num].weight;{原最后树赋予第二}
AT[2].adr:=AT[num].adr; {跟进结点标号}
num:=num-1; {删除原最后树}
k:=k+1; {增加结点标号}
END;
END;
三、应用:哈夫曼编码
利用哈夫曼树构造的用于通信的二进制编码,称为哈夫曼编码。
例如,有一段电文‘CAST TAT A SA’,统计电文中字母的频度,f('C')=1,f('S')=2,f('T')=3,f(' ')=3,f('A')=4,可用其频度{1,2,3,3,4}为权值生成Huffman树,并在每个叶子上注明对应的字符。树中从根到每个叶子都有一条路径,若对路径上的各分支进行约定,指向左子树根的分支用“0”码表示,指向右子树根的分支用“1”码表示,再取每条路径上的“0”或“1”的序列作为与各个叶子对应的字符的编码,这就是哈夫曼编码。