树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用，直观来看，树是以分支关系定义的层次结构。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。树在计算机领域中也得到广泛的应用，如在编译程序中，可用树来表示源程序的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。本章重点讨论二叉树的存储结构及其各种操作，并研究树和森林与二叉树的转换关系，最后介绍几个应用例子。

1. 树的定义与基本术语

树(Tree)是n(n>=0)个节点的有限集。在任意一棵非空树中：（1）有且仅有一个特定的称为根(root)的结点；（2） 当n大于1时，其余节点可分为m(m>0)个互不相交的有限集T1、T2， …， Tn，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。例如，在下图6.1中，(a)是只有一个根节点的树；(b)是有13个节点的树，其中A是根，其余节点分成3个互不相交的子集： T1={B, E, F, K, L}，T2 = {C, G}， T3={D, H, I, J, M}；T1、T2和T3都是根A的子树，且本身也是一棵树。例如T1，其根为B，其余节点分为两个互不相交的子集：T11={E, K, L}， T12={F}。 T11和T12都是B的子树。而T11中E是根，{K}和{L}是E的两棵互不相交的子树，其本身又是只有一个根节点的树。

上述树的结构定义加上树的一组基本操作就构成了抽象数据类型树的定义。

树的结构定义是一个递归的定义，即在树的定义中又用到了树的概念，它道出了树的固有特性。树还可有其他的表示形式，如下图6.2所示为图6.1(b)中树的各种表示。其中(a)是以嵌套集合（即是一些集合的集体，对于其中任何两个集合，或者不相交，或者一个包含另一个）的形式表示的；(b)是以广义表的形式表示的，根作为由子树森林组成的表的名字写在表的左边；（c)用的是凹入表示法（类似书的编目）。表示方法的多样性，正说明了树结构在日常生活中及计算机程序设计中的重要性。一般来说，分等级的分类方案都可用层次结构来表示，也就是说，都可导致一个树结构。

下面列出树结构中的一些基本术语。

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树称为结点的度(Degree)。例如，在图6.1(b)中， A的度为3，C的度为1，F的度为0。度为0的节点称为叶子(Leaf)或者终端节点。图6.1(b)中的节点K、L、F、G、M、I、J都是树的叶子。度不为0的节点称为非终端节点或分支节点。除根节点以外，分支节点也称为内部节点。树的度是树内各结点的度的最大值。如图6.1(b)的树的度为3。结点子树的根称为该节点的孩子(Child)，相应地，该结点称为孩子的双亲(Parent)。例如，在图6.1(b)所示的树中，D为A的子树T3的根，则D是A的孩子，而A则是D的双亲，同一个双亲的孩子之间互称兄弟(Sibling)。例如，H、I和J互为兄弟。将这些关系进一步推广，可认为D是M的祖父。结点的祖先是从根到该结点所经分支上的所有节点。例如，M的祖先为A、D和H。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。如B的子孙为E、K、L和F。

结点的层次(Level)从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第l层，则其子树的根就在第l+1层。其双亲在同一层的结点互为堂兄弟。例如，结点G与E、F、H、I、J互为堂兄弟。树中结点的最大层次称为树的深度(Depth)或高度。图6.1(b)所示的树的深度为4。

如果将树中结点的各子树看成从左到右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。

森林(Forest)是m(m>=0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此，也可以森林和树相互递归的定义来描述树。

就逻辑结构而言，任何一棵树是一个二元组Tree=(root, F)，其中： root是数据元素，称做树的根节点；F是m(m>=0)棵树的森林， F=(T1, T2, …, Tm)，其中Ti = (ri, Fi)称做根root的第i棵子树；当m≠0时，在树根和其子树森林之间存在下列关系：

RF = {<root, ri> | i = 1,2,...,m,  m>0}

这个定义将有助于得到森林和树与二叉树之间转换的递归定义。

树的应用广泛，在不同的软件系统中树的基本操作集不尽相同。

2. 二叉树

在讨论一般树的存储结构及其操作之前，我们首先研究一种称为二叉树的抽象数据类型。

2.1 二叉树的定义

二叉树(Binary Tree)是另一种树形结构，它的特点是每个节点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。

抽象数据类型二叉树的定义如下：

上述数据结构的递归定义表明二叉树或为空，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。由于这两棵子树也是二叉树，则由二叉树的定义，它们也可以是空树。由此，二叉树可以有5种基本形态，如下图6.3所示：

在上一节所引入的有关树的术语也都适用于二叉树。

2.2 二叉树的性质

完全二叉树和满二叉树是两种特殊形态的二叉树。

一棵深度为k且有2^k-1个结点的二叉树称为满二叉树。如图6.4(a)所示是一棵深度为4的满二叉树，这种树的特点是每一层上的结点数都是最大结点树。

可以对满二叉树的结点进行连续编号，约定编号从根节点起，自上而下，自左至右。由此可引出完全二叉树的定义。深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一 一对应时，称之为完全二叉树。如下图6.4(b)所示为一棵深度为4的完全二叉树。显然这种树的特点是：1） 叶子结点只可能在层次最大的两层上出现；2） 对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次必为l或l+1。如下图6.4中(c)和(d)不是完全二叉树。

完全二叉树将在很多场合下出现，下面介绍完全二叉树的两个重要特性。

上图6.5所示为完全二叉树上结点及其左、右孩子结点之间的关系。

2.3 二叉树的存储结构

1. 顺序存储结构

//------ 二叉树的顺序存储表示------

#define MAX_TREE_SIZE 100                         //二叉树的最大结点数

typedef TElemType SqBiTree[MAX_TREE_SIZE];        //0号单元存储根节点

SqBiTree bt;

按照顺序存储结构的定义，在此约定，用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。例如，下图6.6(a)所示为图6.4(b)所示完全二叉树的顺序存储结构。对于一般二叉树，则应将其每个节点与完全二叉树上的结点相对照，存储在一维数组的相应分量中，如图6.4(c)所示二叉树的顺序存储结构如图6.6(b)所示，图中以“0”表示不存在此节点。由此可见，这种顺序存储结构仅适用完全二叉树。因为，在最坏情况下，一个深度为k且只有k个节点的单支树（树中不存在度为2的结点）却需要长度为2^k-1的一维数组。

2. 链式存储结构

设计不同的结点结构可构成不同形式的链式存储结构。由二叉树的定义得知，二叉树的结点（如下图6.7(a)所示）由一个数据元素和分别指向其左、右子树的两个分支构成，则表示二叉树的链表中的结点至少包含3个域： 数据域和左、右指针域，如图6.7(b)所示。有时，为了便于找到结点的双亲，则还可以在结点结构中增加一个指向其双亲结点的指针域，如下图6.7(c)所示。

利用这两种结点结构所得二叉树的存储结构分别称之为二叉链表和三叉链表，如下图6.8所示。

链表的头指针指向二叉树的根结点。容易证得，在含有n个结点的二叉链表中有n+1个空链域。在后面的章节中我们将会看到可以利用这些空链域存储其他有用信息，从而得到另一种链式存储结构————线索链表。以下是二叉链表的定义和部分基本操作的函数原型说明。

//------- 二叉树的二叉链表存储表示------------
typedef struct BiTNode{
	TElemType data;                        
	struct BiTNode *lchild, *right;         //左右孩子指针
}BiTNode, *BiTree;

//--------- 基本操作的函数原型说明(部分) -------------

//按先序次序输入二叉树中结点的值（一个字符），空格表示空树，
//构造二叉链表表示的二叉树
Status CreateBiTree(BiTree &T);

//采用二叉链表存储结构，Visit是对结点操作的应用函数
//先序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。一旦Visit失败，则操作失败
Status PreOrderTraverse(BiTree T, Status (*Visit)(TElemType e));


//采用二叉链表存储结构，Visit是对结点操作的应用函数
//中序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。一旦Visit失败，则操作失败
Status InOrderTraverse(BiTree T, Status (*Visit)(TElemType e));

//采用二叉链表存储结构，Visit是对结点操作的应用函数
//后序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。一旦Visit失败，则操作失败
Status PostOrderTraverse(BiTree T, Status (*Visit)(TElemType e));


//采用二叉链表存储结构，Visit是对结点操作的应用函数
//层序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。一旦Visit失败，则操作失败
Status LevelOrderTraverse(BiTree T, Status (*Visit)(TElemType e));

在不同的存储结构中，实现二叉树的操作方法也不同，如找节点x的双亲PARENT(T, e)，在三叉链表中很容易实现，而在二叉链表中则需要从根指针出发巡查。由此，在具体应用中采用什么存储结构，除根据二叉树的形态之外，还应考虑需进行何种操作。