1、树的定义和基本术语

1.1 树的定义

定义：树(Tree)是n(n>=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：

(1)有且仅有一个特定的称为根(Root)的结点；
(2)其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。
要求子树都非空，使子树的个数（和树的结构）能有明确定义：

结点个数为0 的树称为空树

一棵树可以只有根但没有子树（m = 0），这是一棵单结点的树，只包含一个根结点

树是一种层次性结构：

子树的根看作是树根的下一层元素

一棵树里的元素可以根据这种关系分为一层层的元素

一棵树（除树根外）可能有多棵子树，根据是否认为子树的排列顺序有

意义，可以把树分为有序树和无序树两种概念。例如，普通的树一般是无序的，二叉搜索树BST是有序的。

1.2 树的基本术语

父结点和子结点（是相对定义的）：

一棵树的根结点称为该树的子树的根结点的父结点
子树的根是树根的子结点

边：从父结点到子结点的连线（注意，边有方向）

兄弟结点：父结点相同的结点互为兄弟结点

树叶、分支结点：没有子结点的结点称为树叶，树中的其余结点称为分支结点（注意：分支结点可以只有一个分支）

祖先和子孙：基于父结点/子结点关系和传递性，可以确定相应的传递
关系，称为祖先关系或子孙关系。由这两个关系决定了一个结点的祖先结点，或子孙结点

度数：一个结点的子结点个数称为该结点的度数，显然树叶的度数为0
一棵树的度数就是它里面度数最大的结点的度数

路径，路径长度：

从一个祖先结点到其子孙结点的一系列边称为树中一条路径。显然，从一棵树的根到树中任一个结点都有路径，且路径唯一
路径中边的条数称为路径长度，认为每个结点到自身有长0 的路径

结点的层数：

树根到结点的路径长度是该结点的层数
结点都有层数，根所在的层为0

高度（或深度）：

树的高度或深度是树中结点的最大层数（最长路径的长度）加1
是树的整体性质，空树高度为0，只有根结点的树高度为1

结点的顺序（最左，…，仅在考虑有序树时有意义）

树林：m（m ≥ 0）棵互不相交的树的集合

一棵非空树是一个二元组Tree = (r, F)，其中

r 是树的根结点
F 是m（m ≥ 0）棵子树构成的树林
F = (T1, T2,…, Tm)。其中Ti 称为根r 的第i 棵子树（这是有序树的
情况。对于无序树F 是一个集合，F = {T1, T2,…, Tm} ）

注意树与树林的关系：

树由根和子树树林构成
树林由一集树组成
树和树林可以相互递归定义

2、二叉树

二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树 相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。

2.1 二叉树的定义

定义：二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。

这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。二查树不是树的特殊情况，它们是两个概念。

二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。下图列出二差树的5种基本形态。

2.2 二叉树的性质

二叉树具有下列重要性质：

性质1： 在二叉树的第i层上至多有2i-1个结点(i>=1)。

采用归纳法证明此性质。

当i=1时，只有一个根结点，2i-1=20 =1,命题成立。

现在假定多所有的j，1<=j<i,命题成立，即第j层上至多有2j-2个结点，那么可以证明j＝i时命题也成立。由归纳假设可知，

第i－1层上至多有2i-2结点。

由于二叉树每个结点的度最大为2，故在第i层上最大结点数为第i－1层上最大结点数的二倍，

即2×2i-2＝2i-1。

命题得到证明。

性质2：深度为k的二叉树至多有2k－1个结点（k>=1).

深度为k的二叉树的最大的结点时为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数，： Eki=1（第i层上的最大结点数）= Eki=12i-1=2k –1

性质3： 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。

设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有：N＝n0＋n1＋n2

再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数，则有：N＝B＋1。

由于这些分支都是由度为1和2的结点射出的，所有有：

B＝n1+2*n2 (1)
N＝B＋1＝n1＋2×n2＋1 （2)

由式（1）和（2）得到：

n0+n1+n2=n1+2*n2+1
  n0＝n2＋1

下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树。

一棵深度为k且由2k-1个结点的二叉树称为满二叉树。图(a)就是一棵满二叉树，对结点进行了顺序编号。

如果深度为k、由n个结点的二叉树中个结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，则称这样的二叉树为完全二叉树

图（b）、（c）是2棵非完全二叉树。满二叉树是完全二叉树的特例。

完全二叉树的特点是：

（1)所有的叶结点都出现在第k层或k－1层。

（2）错任一结点，如果其右子树的最大层次为1，则其左子树的最大层次为1或i＋1。

性质4：具有n个结点的完全二叉树的深度为[log2n]＋1。

符号【x】表示不大于x的最大整数。

假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-1－1<n<=2k-1 或 2k-1<=n<2k

取对数得到：k－1<log2n<k 因为k是整数。所以有：k＝【log2n】＋1。

性质5： 如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第【log2n】+1层，每层从左到右),则对任一结点i（1<=i<=n),有：

（1）如果i＝1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲是结点【i/2】。

（2）如果2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。

（3）如果2i＋1>n，则结点i无右孩子；否则，其右孩子是结点2i＋1。

在此过程中，可以从（2）和（3）推出（1），所以先证明（2）和（3）。

对于i＝1，由完全二叉树的定义，其左孩子是结点2，若2>n，即不存在结点2，此是，结点i无孩子。结点i的由孩子也只能是结点3，

若结点3不存在，即3>n，此时结点i无右孩子。

对于i>1，可分为两种情况：

（1）设第j（1<=j<=[log2n])层的第一个结点的编号为i，由二叉树的性质2和定义知i＝2j-1

结点i的左孩子必定为的j＋1层的第一个结点，其编号为2j＝2×2j-1＝2i。如果2i>n，则无左孩子：

（2）假设第j（1<=j<=[log2n])层上的某个结点编号为i（2e(j-1)<=i<=2ej-1),且2i＋1<n，其左孩子为2i，右孩子为2i＋1，

则编号为i＋1的结点时编号为i的结点的右兄弟或堂兄弟。若它有左孩子，则其编号必定为2i＋2＝2×（i＋1）：若它有右孩子，

则其编号必定为2i＋3＝2×（i＋1）＋1。

当i＝1时，就是根，因此无双亲，当i>1时，如果i为左孩子，即2×（i/2)=i,则i/2是i的双亲；

如果i为右孩子，i＝2p+1,i的双亲应为p，p＝（i－1）/2=[i/2]. 证毕。

2.3 二叉树的存储结构

2.3.1 顺序存储结构

它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，

结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法。

从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，

一个深度为H且只有H个结点的右单支树确需要2h-1个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！

2.3.2 链式存储结构