TyvjP1442送货 / Poj2418 Hardwood Species — 二叉查找树的应用

Note: 本文最初于 2011年 在 hi.baidu.com/lydrainbowcat 发表。

二叉排序树，在排序与检索方面应用还是挺广的。

二叉排序树，就是对于其中任意一个结点，满足如下基本性质：

（1）其左子树为空or其左子树上所有元素的值均小于该结点的值。

（2）其右子树为空or其右子树上所有元素的值均大于该结点的值。

所以二叉排序树在排序与检索方面当然有着很大的应用。其他方面当然应用也很大，比如线段树就是一种特殊的二叉排序树，有关线段树的介绍在本博客中也有，在这里我们主要阐述在排序与检索中的应用。

二叉排序树进行排序的时间复杂度为O(nlogn)，退化为一条链时就成了O(n^2)，在解决重复数值较多的排序问题中要明显优于快速排序，一般问题中比快排略慢。

由于二叉排序树不像线段树的填充的那么完全，空的地方很多，所以不宜使用线段树那样左子树num*2，右子树num*2+1的编号形式，而是应该采用链表存储。由于真链表写着麻烦，我更倾向于使用顺序表和数组模拟链表解决。

我这里给出的代码是很朴素的二叉排序树，但是代码非常的简短易懂，对于接触二叉排序树不多的oier非常适用。

TYVJ 1442：

 var
 t:array[0..5000000]of record l,r:longint; dat:real; end;
 n,tot,i:longint;
 a:real;
procedure insert(num:longint);
 begin
  if a<t[num].dat then
   if t[num].l<>0 then insert(t[num].l)
   else begin
    inc(tot);
    t[tot].dat:=a;
    t[num].l:=tot;
   end;
  if a>t[num].dat then
   if t[num].r<>0 then insert(t[num].r)
   else begin
    inc(tot);
    t[tot].dat:=a;
    t[num].r:=tot;
   end;
 end;
procedure print(num:longint);
 begin
  if t[num].l<>0 then print(t[num].l);
  write(t[num].dat:0:2,' ');
  if t[num].r<>0 then print(t[num].r);
 end;
begin
 readln(n);
 read(a);
 t[1].dat:=a;
 tot:=1;
 for i:=2 to n do
  begin
   read(a);
   insert(1);
  end;
 print(1);
 writeln;
end.

POJ 2418：

Source Code

Problem: 2418		User: lydliyudong
Memory: 21100K		Time: 5407MS
Language: Pascal		Result: Accepted

• Source Code

var
 t:array[0..1000010]of record l,r,num,dat:longint; str:ansistring; end;
 n,tot:longint;
 s:ansistring;

procedure insert(num:longint);
 begin
  if s<t[num].str then
   if t[num].l<>0 then insert(t[num].l)
   else begin
    inc(tot);
    t[num].l:=tot;
    t[tot].str:=s;
    t[tot].dat:=1;
   end
  else if s>t[num].str then
   if t[num].r<>0 then insert(t[num].r)
   else begin
    inc(tot);
    t[num].r:=tot;
    t[tot].str:=s;
    t[tot].dat:=1;
   end
  else inc(t[num].dat);
 end;

procedure print(num:longint);
 begin
  if t[num].l<>0 then print(t[num].l);
  writeln(t[num].str,' ',t[num].dat/n*100:0:4);
  if t[num].r<>0 then print(t[num].r);
 end;

begin
 n:=1; tot:=1;
 readln(s);
 t[1].str:=s;
 t[1].dat:=1;
 while not seekeof do
  begin
   inc(n);
   readln(s);
   insert(1);
  end;
 print(1);
end.