一棵树(tree)是由n(n>0)个元素组成的有限集合，其中:

(1)每个元素称为结点(node);

(2)有一个特定的结点，称为根结点或根(root);

(3)除根结点外，其余结点被分成m(m>=0)个互不相交的有限集合，而每个子集又都是一棵树(称为原树的子树)

树的度--也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。

树的深度--组成该树各结点的最大层次，如上图，其深度为4;

根结点的层次为1，其他结点的层次等于它的父结点的层次数加1.

对于一棵子树中的任意两个不同的结点，如果从一个结点出发，按层次自上而下沿着一个个树枝能到达另一结点，称它们之间存在着一条路径。可用路径所经过的结点序列表示路径，路径的长度等于路径上的结点个数减1.

指若干棵互不相交的树的集合

树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的系统的访问，即依次对树中每个结点访问一次且仅访问一次。树的3种最重要的遍历方式分别称为前序遍历、中序遍历和后序遍历。以这3种方式遍历一棵树时，若按访问结点的先后次序将结点排列起来，就可分别得到树中所有结点的前序列表，中序列表和后序列表。相应的结点次序分别称为结点的前序、中序和后序。

树的这3种遍历方式可递归地定义如下:

§ 如果T是一棵空树，那么对T进行前序遍历、中序遍历和后序遍历都是空操作，得到的列表为空表。

§ 如果T是一棵单结点树，那么对T进行前序遍历、中序遍历和后序遍历都只访问这个结点。这个结点本身就是要得到的相应列表。

§ 否则，设T如图6所示，它以n为树根，树根的子树从左到右依次为T1,T2,..,Tk，那么有:

§ 对T进行前序遍历是先访问树根n,然后依次前序遍历T1,T2,..,Tk。

§ 对T进行中序遍历是先中序遍历T1，然后访问树根n，接着依次对T2,T2,..,Tk进行中序遍历。

§ 对T进行后序遍历是先依次对T1,T2,..,Tk进行后序遍历，最后访问树根n。

排序是一种十分重要的运算。所谓排序就是把一堆杂乱无章的元素按照某种次序排列起来，形成一个线性有序的序列。二叉排序树是利用二叉树的结构特点来实现对元素排序的。

一、二叉排序树的定义

二叉排序树或者是空树，或者是具有如下性质的二叉树:

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;

下面是在这个存储结构上实现的构造哈夫曼树的算法:

Procedure Huffmantree(VAR W:ARRAY[1..n]OF real;VAR TR:tree);

VAR AT:A;

BENGIN

FOR i:=1 TO n DO{实现第(1)步}

BEGIN

TR.weight:=W;{将权值放在树叶中}

TR.Lc:=0;

TR.Rc:=0;

AT.weight:=TR.weight;{用AT存放当前森林的根}

AT.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"的序列作为与各个叶子对应的字符的编码，这就是哈夫曼编码。