定义

基本概念(度 深度 层次 路径 森林)

树的表示(父亲数组表示法 儿子链表表示法 左儿子右兄弟表示法)

树的遍历

树的应用(二叉排序树 Huffman树)

二叉树

树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。

定义

一棵树（tree）是由n（n>0）个元素组成的有限集合，其中：

（1）每个元素称为结点（node）；

（2）有一个特定的结点，称为根结点或根（root）；

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

基本概念

度

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

深度

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

层次

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

路径

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

森林

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

树的表示

父亲数组表示法

设T是一棵树，表示T的一种最简单的方法是用一个一维数组存储每个结点，数组的下标就是结点的位置指针，每个结点中有一个指向各自的父亲结点的数组下标的域，这样可使Parent操作非常方便。类型定义如下：

Type
TPosition=integer; {结点的位置类型为整型}
NodeType=Record
Label:LabelType; {该结点的标号}
Parent:TPosition; {该结点的父亲的数组下标，对于根结点该域为0}
End;
TreeType=Record
NodeCount:integer; {树的结点的总数目}
Node:Array [1..MaxNodeCount] of NodeType;{存储树的结点}
End; 　由于树中每个结点的父亲是唯一的，所以上述的父亲数组表示法可以唯一地表示任何一棵树。在这种表示法下，寻找一个结点的父结点只需要O(1)时间。在树中可以从一个结点出发找出一条向上延伸到达其祖先的道路，即从一个结点到其父亲，再到其祖父等等。求这样的道路所需的时间正比于道路上结点的个数。在树的父亲数组表示法中，对于涉及查询儿子和兄弟信息的树操作，可能要遍历整个数组。为了节省查询时间，可以规定指示儿子的数组下标值大于父亲的数组下标值，而指示兄弟结点的数组下标值随着兄弟的从左到右是递增的。

儿子链表表示法

树的另一种常用的表示方法就是儿子链表表示法。这种表示法用一个线性表来存储树的所有结点信息，称为结点表。对每个结点建立一个儿子表。儿子表中只存储儿子结点的地址信息，可以是指针，数组下标甚至内存地址。由于每个结点的儿子数目不定，因此儿子表常用单链表来实现，因此这种表示法称为儿子链表表示法。这种实现法与图的邻接表表示法类似。下图是一个儿子链表表示法的示意图。

图3 树的儿子链表实现

图3中儿子链表结构表示的树如图4所示，树中各结点存放于一个数组实现的表中，数组下标作为各结点的指针。每一个数组元素（即每一个结点）含有一个儿子表，在图3中儿子表是用单链表来实现的，当然也可以用其他表的实现方式来实现儿子表，比如说游标方式(静态链表)。但由于每个结点的儿子数目不确定，所以一般不用数组来实现儿子表，但可以用数组来实现结点表，就如图3所示。在图3中可以看到，位于结点表第一个位置的结点(未必是根结点)有两个儿子结点，从左到右的两个儿子结点分别位于结点表的第2和第3个位置。因为图3中的结点表用数组实现，所以结点的标号就是结点在结点表中的数组下标。如图4所示。

图4 图3中儿子链表所表示的树

为了指明树的根结点的位置，我们可以用一个变量Root记录根结点在结点表中的位置。有了根结点的位置，就可以利用儿子表依次找到树中所有的结点。

儿子链表表示的树的类型定义如下：

Type
{======================
NodeListType是一个元素为NodeType类型的线性表，其位置类型为TPosition，
NodeListType定义了结点表的类型；
ChildrenListType是一个元素为TPosition类型的线性表， ChildrenListType定义了儿子表的类型
=======================}
TPosition=....
ChildrenListType=...
NodeType=Record {结点的类型}
Label:LabelType; {结点的标号}
Children:ChildrenListType;{结点的儿子表}
End;
NodeListType=...
TreeType=record
root:TPosition; {记录树根在结点表中的位置}
Node:NodeListType; {结点表}
end; 　其中NodeListType是一个元素为NodeType类型的线性表，其位置类型为TPosition，NodeListType定义了结点表的类型；ChildrenListType是一个元素为TPosition类型的线性表， ChildrenListType定义了儿子表的类型。以上类型定义并不考虑表的具体实现方式，如果假设结点表和儿子表都用单链表实现，则类型定义可以具体实现如下：

{儿子链表实现树的类型定义的一个具体实例，结点表和儿子表都用单链表实现}
Type
TPosition=^NodeType; {结点表的位置类型}
ChildrenNodeType=record {儿子表的结点项的类型}
child:TPosition; {指向儿子结点的位置指针}
next:^ChildrenNodeType; {指向下一个儿子表项的指针}
end;
NodeType=Record {结点的类型定义为单链表}
Label:LabelType; {结点的标号}
Children:^ChildrenNodeType;{指向儿子表的指针}
Next:TPosition;
End;
TreeType=^NodeType; {树的类型定义为结点指针类型} 　注意以上的定义只是一种具体情况，实际应用中结点表和儿子表可能用数组、链表等任何一种表的实现方式实现。

左儿子右兄弟表示法

树的左儿子右兄弟表示法又称为二叉树表示法或二叉链表表示法。每个结点除了data域外，还含有两个域，分别指向该结点的最左儿子和右邻兄弟。这种表示法常用二叉链表实现，因此又称为二叉链表表示法。但是实际应用中常用游标(静态链表)来代替链表，请参见表的游标实现。

若用指针实现，其类型定义为：

Type
TPosition=^NodeType;
NodeType=record
Label:LabelType;
Leftmost_Child,Right_Sibling:TPosition;
end;
TreeType=TPosition; 　若用游标实现，其类型定义为:

Type
TPosition=integer;
NodeType=record
Label:LabelType;
Leftmost_Child,Right_Sibling:TPosition;
end;
CellspaceType=array [1..MaxNodeCount] of NodeType;
TreeType=TPosition;
var
Cellspace:CellspaceType;
Tree:TreeType; 　此时树类型TreeType是整数类型，它指示树根在cellspace中的游标。例如图5(a)中树的左儿子右兄弟表示法的指针和游标实现分别如图5(b)和(c)所示。

(a)

(b)

(c)

图5 树的左儿子右兄弟表示法

用树的左儿子右兄弟表示法可以直接实现树的大部分操作，只有在对树结点作Parent操作时需遍历树。如果要反复执行Parent操作，可在结点记录中再开辟一个指向父结点的指针域，也可以利用最右儿子单元中的Right_Sibling作为指向父结点的指针(否则这里总是空指针)。当执行Parent(v)时，可以先通过Right_Sibling逐步找出结点v的最右兄弟，再通过最右兄弟的Right_Sibling(父亲指针)找到父结点。这个结点就是结点v的父亲。在这样的表示法下，求一个结点的父亲所需要的时间正比于该结点右边的兄弟个数。不过，这时每个记录中需要多用一位(bit)空间，用以标明该记录中的right_sibling是指向右邻兄弟还是指向父亲。

考虑到对于现在的计算机，内存已经不是很重要的限制因素了。我们下面就采取增加一个parent域的方案，以改进左儿子右兄弟表示法中Parent操作的效率。因此重新定义树的类型如下：

若用指针实现，其类型定义为：

Type
TPosition=^NodeType;
NodeType=record
Label:LabelType;
Parent,Leftmost_Child,Right_Sibling:TPosition; {增加一个Parent域}
end;
TreeType=TPosition;
var
Tree:TreeType; 　若用游标实现，其类型定义为:

Type
TPosition=integer;
NodeType=record
Label:LabelType;
Parent,Leftmost_Child,Right_Sibling:TPosition; {增加一个Parent域}
end;
CellspaceType=array [1..MaxNodeCount] of NodeType;
TreeType=TPosition;
var
Cellspace:CellspaceType;
Tree:TreeType;

树的遍历

树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的系统的访问，即依次对树中每个结点访问一次且仅访问一次。树的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、对以后的各个数据，逐个插入结点，而且规定：在插入过程的每一步，原有树结点位置不再变动，只是将新数据的结点作为一个叶子结点插入到合适的位置，使树中任何结点的数据与其左、右子树结点数据之间的关系仍然符合对二叉排序树的要求。

Huffman树

一、哈夫曼树的含义：哈夫曼树是一种带权路径长度最短的树。

所谓路径长度就是某个端结点到树的根结点的距离，等于该端结点的祖先数，或该结点所在层数减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[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”的序列作为与各个叶子对应的字符的编码，这就是哈夫曼编码。

二叉树

二叉树是一类非常重要的树形结构，它可以递归地定义如下：

二叉树T是有限个结点的集合，它或者是空集，或者由一个根结点u以及分别称为左子树和右子树的两棵互不相交的二叉树u(1)和u(2)组成。若用n,n1和n2分别表示T，u(1)和u(2)的结点数，则有n=1+n1+n2 。u(1)和u(2)有时分别称为T的第一和第二子树。

因此，二叉树的根可以有空的左子树或空的右子树，或者左、右子树均为空。

二叉树具有以下的重要性质：

高度为h≥0的二叉树至少有h+1个结点； 高度不超过h(≥0)的二叉树至多有2h+1-1个结点； 含有n≥1个结点的二叉树的高度至多为n-1； 含有n≥1个结点的二叉树的高度至少为 logn ，因此其高度为Ω(logn)。 详见二叉树词条。