二叉树的应用

二叉树的应用
1. 哈夫曼树与哈夫曼码

树的路径长度：一棵树的每一个叶结点到根结点的路径长度的和。

带权二叉树：给树的叶结点赋上某个实数值（称叶结点的权）。

带权路径长度：各叶结点的路径长度与其权值的积的总和。

哈夫曼树（最优二叉树）：带权路径长度最小的二叉树。

如何构建哈夫树：（思想是：权越大离跟越近）

programgojiantree;
const n=4;m=7;
type node=record
     w:real;
     parent,lchild,rchild:0..m
     end;
    htree=array[1..m] of node;
var htree1:htree;
procedure gjtree(var ht:htree);
var i,j:integer;
    small1,small2:real;
   p1,p2:0..m;
begin
for i:=1 to m do
with ht do
  begin
  w:=0;lchild:=0;rchild:=0;parent:=0;
  end;
for i:=1 to n do read(ht.w);
for i:=n+1 to m do
  begin
  p1:=0;p2:=0;
  small1:=1000;small2:=1000;
  for j:=1 to i-1 do
   if ht[j].parent=0 then
          if ht[j].w<small1then
            beginsmall2:=small1;small1:=ht[j].w;p2:=p1;p1:=j end
             elseif ht[j].w<small2 then begin small2:=ht[j].w;p2:=j end;
  ht[p1].parent:=i;
  ht[p2].parent:=i;
  ht.lchild:=p1;
  ht.rchild:=p2;
  ht.w:=ht[p1].w+ht[p2].w;
  end;
end;
begin
gjtree(htree1);
end.

哈夫曼码：哈夫曼树的非叶结点到左右孩子的路径分别用0，1 表示，从根到叶的路径序列即为哈夫曼码。

哈夫曼码是不会发生译码多义性的不等长编码，广泛应用实际中。

（原因是任何一字符的编码不是更长编码的前缀部分，为什么？）

2.排序二叉树

排序二叉树：每一个参加排列的数据对应二叉树的一个结点，且任一结点如果有左（右）子树，则左（右）子树各结点的数据必须小（大）于该结点的数据。中序遍历排序二叉树即得排序结果。程序如下：

program pxtree;
const
a:array[1..8] of integer=(10,18,3,8,12,2,7,3);
type point=^nod;
     nod=record
     w:integer;
     right,left:point ;
     end;
var root,first:point;k:boolean;i:integer;
procedure hyt(d:integer;var p:point);
begin
  if p=nil then
   begin
    new(p);
    with p^ do begin w:=d;right:=nil;left:=nil end;
    if k then begin root:=p; k:=false end;
   end
  else with p^ do if d>=w then hyt(d,right) else hyt(d,left);
end;
procedure hyt1(p:point);
begin
  with p^ do
   begin
    if left<>nil then hyt1(left);
    write(w:4);
    if right<>nil then hyt1(right);
   end
end;
begin
first:=nil;k:=true;
for i:=1 to 8 do hyt(a,first);
hyt1(root);writeln;