数据结构---树

树是一种重要的非线性数据结构，它是数据元素(在树中称为结点)分支关系组织起来的结构，很像自然界中的树。树型结构是信息的重要组织形式，在竞赛中经常被应用。一切具有层次关系的问题都可以用树来描述。 一、树的概述 （一）树的定义

1、树(Tree)是n(n>=0)个结点的有限集合。在一棵非空树中： (1) 有且仅有一个特定的称为根的结点;

(2) 当n>1时其余结点可分为m(m>0)个互不相交的有限集T1,T2...Tm,其中,每一个集合本身又是一棵树, 并且称为根的子树(subtree)。例如,在下图中,(b)是只有一个根结点的树;(a)是有 13个结点的树,其中A是根,其余结点分成三个互不相交的子树：

2、树结构中的一些基本术语：

  

结点的度：结点拥有的子树数。 叶子（终端结点）：度为零的结点。 非终端结点（分支结点）：度不为零的结点。



树的度：树内各结点的度的最大值。

（二） 二叉树定义

1、 二叉树(binary tree)是另一种树型结构，它的特点是每个结点至多只有二棵子树，并且二叉树的子树有左右之分。 特例1：空树和只有根结点的树也为二叉树

特例2：若二叉树每一层上的结点个数都达到最大值，则该树为满二叉树 特例3：若二叉树结点中，只有最下两层的结点的度小于2，且最下层的结点都集中中最左边的若干位置，则该树称为完全二叉树。 两个重要的概念：

完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中

在该层最左边的若干位置的二叉树；

满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的

二叉树,。满二叉树也是完全二叉树。

二叉树是一种数据结构 ,下图是各种形态的二叉树.：

(1) 为空二叉树 (2)只有一个根结点的二叉树 (3)右子树为空的二叉树 (4)左子树为空的二叉树 (5)满二叉树 （6）完全二叉树

（5）

（6）

2、二叉树的性质：

(1) 在二叉树中，第i层的结点总数不超过2^(i-1)；

(2) 深度为h的二叉树最多有2h-1个结点(h>=1)，最少有h个结点； (3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

二、二叉树的存储结构 （一） 顺序存储结构

连续的存储单元存储二叉树的数据元素。以向量(一维数组 )作它的存储结构，将二叉树中编号为i的结点的数据元素存放在分量bt[i]中。但这种顺序存储结构仅适合于完全二叉树,而一般二叉树也按这种形式来存储,这将造成存贮浪费，往往以“0”表示不存在此结点。

完全二叉树常采用顺序存储方式。按结点层次从小到大、同一层从左到右顺序排列。

例：下面是利用完全二叉树特性，用顺序表来存储的一棵二叉树，结点数据为字符型(结点层次从小到大、同一层从左到右顺序存储,#表示空结点,@表示存储数据结束)。现要求画出该存储结构对应的二叉树示意图。 1 A 2 B 3 C 4 # 5 # 6 D 7 E 8 # 9 # 10 11 12 13 14 15 # # G # F @ type node=record

data:datatype l,r:integer; end;

var tr:array[1..n] of node; （二）链式存储结构

由二叉树的定义得知二叉树的结点由一个数据元素和分别指向左右子树的两个分支构成,则表示二叉树的链表中的结点至少包含三个域:数据域和左右指针域,如下图(b)所示。有时,为了便于找到结点的双亲,则还可在结点结构中增加一个指向其双亲受的指针域，如下图 (c)所示。

type btree=^node；

node=record data:datatye; lchild,rchild:btree; end;

三、 遍历二叉树

遍历二叉树(traversing binary tree)的问题， 即如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。 其中常见的有三种情况：分别称之为先(根)序遍历，中(根)序遍历和后(根)序遍历。

（一）前序遍历

前序遍历运算：即先访问根结点，再前序遍历左子树，最后再前序遍历右子树。前序遍历运算访问二叉树各结点是以根、左、右的顺序进行访问的。例如：

按前序遍历此二叉树的结果为：Hello!How are you?

proc preorder(bt:bitreprtr) if (bt<>null)[ print(bt^);

preorder(bt^.lchild); preorder(bt^.rchild);] end;

（二）中序遍历

中序遍历运算：即先中前序遍历左子树，然后再访问根结点，最后再中序遍历右子树。中序遍历运算访问二叉树各结点是以左、根、右的顺序进行访问的。例如：

按中序遍历此二叉树的结果为：a*b-c

proc inorder(bt:bitreprtr) if (bt<>null)[

inorder(bt^.lchild); print(bt^);

niorder(bt^.rchild);] end;

（三）后序遍历

后序遍历运算：即先后序遍历左子树，然后再后序遍历右子树，最后访问根结点。后序遍历运算访问二叉树各结点是以左、右、根的顺序进行访问的。例如：

按后序遍历此二叉树的结果为：Welecome to use it!

proc postorder(bt:bitreprtr) if (bt<>null)[

postorder(bt^.lchild); postorder(bt^.rchild);] print(bt^); end;

例题分析:

例1：下面二叉树对应的先、中、后序遍历分别是什么？

先（根）序遍历 ABDFGCEH 中（根）序遍历 BFDGACHE 后（根）序遍历 FGDBHECA

例2：给出一棵二叉树的中序遍历：DBGEACHFI 与后序遍历：DGEBHIFCA ，画出此二叉树。

例3：已知，按中序遍历二叉树的结果为：abc 。问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。

A B B A C A B B C A C A B C C 例4：用顺序存储方式建立一棵如图所示的二叉树，并对其进行先序遍历。

program tree1; const n=15;

type node=record data:char; l,r:0..n; end;

var tr:array[1..n] of node; e:array[1..n] of 0..1; i,j:integer; procedure jtr; var i:integer; begin

for i:=1 to n do with tr[i] do readln(data,l,r); end;

procedure search(m:integer); begin with tr[m] do begin write(data);

if l<>0 then search(l); if r<>0 then search(r); end; end;

begin

jtr;search(1);writeln; end.

例5： 用链表存储方式生成上述二叉树，中序遍历之。 1.将上述二叉树用广义表表示为A(B(D,E(G)),C(F(,H))) 2.根据广义表串（以#结束）生成二叉树。 program ltree; const n=8; type trlist=^node; node=record da:char; l,r:trlist; end;

var s:array[1..n] of trlist; p,root:trlist; ch:char; top,k:integer;

procedure creat(var head:trlist); begin read(ch); top:=0;

while ch<>'#' do begin

case ch of

'A'..'Z':begin new(p);p^.da:=ch;p^.l:=nil;p^.r:=nil; if top<>0 then case k of 1:s[top]^.l:=p; 2:s[top]^.r:=p; end end;

'(':begin top:=top+1;s[top]:=p;k:=1;end; ')': top:=top-1; ',': k:=2; end; read(ch); end; head:=s[1]; end;

procedure inorder(head:trlist); begin

if head^.l<>nil then inorder(head^.l); write(head^.da);

if head^.r<>nil then inorder(head^.r); end; begin

write('Input tree string:'); creat(root); inorder(root); end.

四、二叉树的应用： （一） 哈夫曼树与哈夫曼码

树的路径长度：一棵树的每一个叶结点到根结点的路径长度的和。 带权二叉树：给树的叶结点赋上某个实数值（称叶结点的权）。 带权路径长度：各叶结点的路径长度与其权值的积的总和。 哈夫曼树（最优二叉树）：带权路径长度最小的二叉树。 如何构建哈夫树：（思想是：权越大离根越近） program gojiantree; const n=4;m=7; {m=2n-1} 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[i] do begin

w:=0;lchild:=0;rchild:=0;parent:=0; end;

for i:=1 to n do read(ht[i].w); {1—n为叶子结点，n+1至2n-1为中间结点， 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].wbegin small2:=small1;small1:=ht[j].w;p2:=p1;p1:=j end else if ht[j].wht[i].w:=ht[p1].w+ht[p2].w; end; end;

{选择父指针为0且权值最小的两个结点}

根为2n-1}

begin

gjtree(htree1); end.

Program huffman_tree(input,output); const max=32767;n=20;m=2*n-1 Type tnode=RECORD data:integer; Lc,Rc:integer; END;

Var tree:ARRAY[0..m] of tnode; weight:ARRAY[0..n] of integer; im,num:integer;

procedure initial; {输入} var i:integer; begin

write('First input num(<',n:2,')'); readln(num);

writeln('Please input weight:'); for i:=0 to num-1 do read(weight[i]) end;

function minimum:integer; {选择父指针为0且权值最小的结点} var i:integer; begin min:=max;

for i:=0 to num-1 do if (min>weight[i]) then begin min:=weight[i]; im:=i; end;

weight[im]:=max; minimum:=min; end;

procedure huffman; {构建哈夫曼树} var i,k:integer; begin

for i:=num to 2*num-1 do begin

tree[i].Lc:=minimum; tree[i].Rc:=minimum;

tree[i].data:=tree[i].Lc:+tree[i].Rc; weight[im]:=tree[i].data

end; writeln;

writeln('The result of huffman tree:'); k:=1;

for i:=2*num-1 downto num do begin

write(tree[i].data:6,':',tree[i].Lc:3,tree[i].Rc:3); if (k mod 3=0) then writeln; k:=k+1; end ; writeln ; end;

procedure printd; {打印} var i:integer; begin

write('The weight of tree:'); for i:=0 to num-1 do write{weight[i]:3} end;

begin {main} initial;

printd; huffman end.

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

哈夫曼码是不会发生译码多义性的不等长编码，广泛应用实际中。 （二）排序二叉树

排序二叉树：每一个参加排列的数据对应二叉树的一个结点，且任一结点如果有左（右）子树，则左（右）子树各结点的数据必须小（大）于该结点的数据。中序遍历排序二叉树即得排序结果。不需要经过数据交换，而是将数据直接定位，因此效率特别高。 算法：

1、设根结点为空。 2、依次取出一个数据

3、若根结点为空，则用此数据作为根结点的值；否则用此数据与根结点比较； （1）小于根结点，取根结点左结点作下一次比较的根结点，重复3； （2）大于或等于结点，取根结点的右结点作下一次比较的根结点，重复3。 4、用中（根）序遍历法输出分类结果。 程序如下： 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[i],first); hyt1(root);writeln; end.

（三）堆排序

堆：设有数据元素的集合（R1,R2,R3,...Rn)它们是一棵顺序二叉树的结点且有 Ri<=R2i 和Ri<=R2i+1(或>=)

堆的性质：堆的根结点上的元素是堆中的最小元素，且堆的每一条路径上的元素都是有序的。 堆排序的思想是：

1）建初始堆（将结点[n/2],[ n/2]-1,...3,2,1分别调成堆） 2）当未排序完时

输出堆顶元素，删除堆顶元素，将剩余的元素重新建堆。 程序如下： program duipx; const n=8;

type arr=array[1..n] of integer; var a:arr;i:integer;

procedure sift(var a:arr;l,m:integer); var i,j, t:integer;

begin

i:=l;j:=2*i;t:=a[i]; while j<=m do begin

if (ja[j+1]) then j:=j+1; if t>a[j] then

begin a[i]:=a[j];i:=j;j:=2*i; end else exit; end; a[i]:=t; end; begin

for i:=1 to n do read(a[i]); for i:=(n div 2) downto 1 do sift(a,i,n);

for i:=n downto 2 do begin write(a[1]:4); a[1]:=a[i]; sift(a,1,i-1); end;

writeln(a[1]:4); end.

1 引言

排序是计算机数据处理及其它许多软件系统中常用的一种操作。排序的目的通常是为了便于查找或为了适应某些查找算法的需要。例如，在统计高考成绩的系统中，要产生几个表。第一个表按考生的考号从小到大的顺序，列出所有考生的成绩；第二个表按考生的考试成绩从高到低的顺序，列出所有考生的成绩等等。在这样的系统中就要多次进行排序操作。

排序（Sorting）是把一个无序的数据元素序列按某个关键字进行有序（递增或递减）排列的过程。通常，待排序的操作对象称为数据表，它是数据元素（即记录）的有限集合。在每一个数据元素中有多个属性。当某个属性用来区分对象作为排序的依据时，该属性就称为排序关键字（Key）。如上例中的考号、考试成绩等都是排序关键字。在实际应用中，每个数据表用哪个属性作为排序关键字要视具体的应用需要而定。

排序的方法很多，就其全面的性能而言，很难提出一种被认为是最好的方法，每种方法都各有优缺点，适合在不同的环境下使用。就其时间的性能而言，插入排序、冒泡排序、选择排序性能比较接近，而快速排序、堆排序、归并排序则是性能比较接近的另一类。 2 堆排序的原理与技术

堆排序是改进的算法，比较复杂。记录数越多越适合，效率可以明显提高。堆排序是借助于一种称为堆的完全二叉树结构进行排序的，排序过程中，将向量中存储的数据看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中的父结点和子结点之间的内在关系来选择关键字最小或最大的记录。

具体做法是：把待排序的记录存放在数组r[1‥n]中，将r看作一棵二叉树，每个结点表示一个记录，第一个记录r[1]作为二叉树的根，以后各记录r[2]，„，

r[n]依次逐层从左到右顺序排列，构成一棵完全二叉树，任意结点r[i]的左孩子是r[2i]，右孩子是r[2i+1]，双亲是r[i/2]。对这棵完全二叉树的结点进行调整，使各结点的关键字满足条件，r[i]≤r[2i]且r[i]≤r[2i+1]，即每个结点的值均小于或等于它的两个子结点的值，显然在这个堆树中根结点的关键字最小，这种堆被称为“小根堆”。若各结点的值满足r[i]≥r[2i]并且r[i]≥r[2i+1]的堆，称为“大根堆”，大根堆中根结点的关键字值最大。

在堆中，根结点又被称为堆顶元素，当把二叉树转换成大根堆后，堆顶元素最大，把堆顶元素输出，重新调整二叉树的剩余结点，使其成为一个新堆，再输出堆顶元素，便可求得次最大值，如此反复进行，就可得到一个有序序列，这就是利用大根堆排序的基本方法。小堆根的排序方法类似。

堆排序的关键是构造堆，即调整元素间的关系使之形成堆。由二叉树的性质得知，二叉树中序号最大的一个非终点是[n/2]，序号最小的列终结点是序号为1的结点，对这些结点需一一进行调整，使其满足堆的条件。调整过程为：首先把[n/2]号结点元素与其两个孩子中值大者进行比较并交换后，形成以[n/2]为根的子树即为堆，接着用相同的步骤对第[n/2-1]结点进行调整，直至第1个结点。如果在中间调整过程中，由于交换破坏了以其孩子为根的堆，则要对破坏了的堆进行调整，依次类推，直到父结点大于等于左、右孩子的元素结点或者孩子结点为空的元素结点。当这一系列调整过程完成时，即成为一个堆树，这个调整过程也叫做“筛选”。 3 堆排序的实现

3.1 堆排序在成绩管理中的实现

下面给出学生的考试成绩表，如图1所示。每条信息由考号与分数组成。以按分数高低次序来排出每个学生在考试中获得的名次，分数相同的为同一名

次为例，说明堆排序的算法。

这里，二叉树中序号最大的一个非终点是[n/2]，即图中的4号结点268.5，序号最小的列终结点是序号为1的结点，即根结点270.0。调整过程为：首先把4号结点元素268.5与其两个孩子中值大者进行比较，由于左孩子272.5>268.5故将它们交换，则以272.5为根的子树即为堆。接着用相同的步骤对第3个结点进行调整，因其满足条件，则不必交换。直至第1个结点270.0，最终形成初始堆，如图3。

图1 学生考试成绩表

图2 原始数据的二叉树顺序存储形

图3 建立初始堆

排序过程为：先输出堆顶元素292.0，把它放到原数组的最后位置，而原数组最后一个单元存放的是244.5，为了不破坏数据，则把292.0与244.5交换，即r[1]与r[n]（n为9）交换，这时r[n]为最大，接着对r[1]与r[n－1]进行筛选又得到新堆，此时新堆的r[1]为当前最大的元素，再把r[1]与r[n－1]对调，使r[n－1]为次最大，这样，经过n－1次对调、筛选，数组r中的所有元素均按升序排列，堆排序全部完成，如图4所示。

3.2 堆排序的算法描述

下面给出整个排序过程及算法描述。（说明：已经有序的子树部分省去。） heapsort （Recordnode r[ ]，int n） {int i，k；

Struct Recordnode x；

For（i=n/2；i>0；i--） /*建立初始堆*/ Sift（r，i，n）；

For（i=n；i>1；i--） /*进行n－1次循环，完成堆排序*/ { x=r[1]； /*将第一个元素与当前区间的最后一个元素对调*/ r[1]=r[i]； r[i]=x；

sift（r，1，i-1）； /*调用筛选子函数*/ } }

4 结束语

从堆排序的算法知道，堆排序所需的比较次数是建立初始堆与重新建堆所需的比较次数之和，其平均时间复杂度和最坏的时间复杂度均为O（n lbn）。它是一种不稳定的排序方法。

但对应于大量记录，堆排序的效率却是非常高的。