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

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

　　二叉树有5种基本形态,如图1所示.

　　图1二叉树的5种基本形态(其中□表示空)

　　在二叉树中,每个结点至多有两个儿子,并且有左、右之分.因此任一结点的儿子不外4种情况：没有儿子；只有一个左儿子；只有一个右儿子；有一个左儿子并且有一个右儿子.

　　--------------------------------------------------------------------------------

　　注意：二叉树与树和有序树的区别

　　--------------------------------------------------------------------------------

　　二叉树与度数不超过2的树不同,与度数不超过2的有序树也不同.在有序树中,虽然一个结点的儿子之间是有左右次序的,但若该结点只有一个儿子时,就无须区分其左右次序.而在二叉树中,即使是一个儿子也有左右之分.例如图2中(a)和(b)是两棵不同的二叉树.虽然它们与图3中的普通树(作为无序树或有序树)很相似,但它们却不能等同于这棵普通的树.若将这3棵树均看作是有序树,则它们就是相同的了.

　　图2两棵不同的二叉树

　　图3一棵普通的树

　　由此可见,尽管二叉树与树有许多相似之处,但二叉树不是树的特殊情形.

　　二叉树的数学性质

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

　　高度为h≥0的二叉树至少有h+1个结点；

　　高度不超过h(≥0)的二叉树至多有2h+1-1个结点；

　　含有n≥1个结点的二叉树的高度至多为n-1；

　　含有n≥1个结点的二叉树的高度至少为logn,因此其高度为Ω(logn).

　　具有n个结点的不同形态的二叉树的数目在一些涉及二叉树的平均情况复杂性分析中是很有用的.设Bn是含有n个结点的不同二叉树的数目.由于二叉树是递归地定义的,所以我们很自然地得到关于Bn的下面的递归方程：

　　(1)

　　即一棵具有n>1个结点的二叉树可以看成是由一个根结点、一棵具有i个结点的左子树和一棵具有n-i-1个结点的右子树所组成.

　　(1)式的解是

　　(2)

　　即所谓的Catalan数.因此,当n=3时,B3=5.于是,含有3个结点的不同的二叉树有5棵,如图4所示.

　　图4含有3个结点的不同二叉树

　　特殊形态的二叉树

　　满二叉树和近似满二叉树是二叉树的两种特殊情形.

　　一棵高度为h≥0且有2h+1-1个结点的二叉树称为满二叉树.

　　若一棵二叉树至多只有最下面的两层结点的度数小于2,并且最下面一层结点都集中在该层的最左边,则称这种二叉树为近似满二叉树(有时也称为完全二叉树).

　　(a)满二叉树

　　(b)近似满二叉树

　　(c)非近似满二叉树

　　图5特殊形态的二叉树

　　例如图5(a)是一棵高度为3的满二叉树.满二叉树的特点是每一层上的结点数都达到最大值,即对给定的高度,它是具有最多结点数的二叉树.满二叉树中不存在度数为1的结点,每个分枝结点均有两棵高度相同的子树,且叶结点都在最下面一层上.图5(b)是一棵近似满二叉树.显然满二叉树是近似满二叉树,但近似满二叉树不一定是满二叉树.在满二叉树的最下层上,从最右结点开始连续往左删去若干个结点后得到的二叉树是一棵近似满二叉树.因此,在近似满二叉树中,若某个结点没有左儿子,则它一定没有右儿子,即该结点是一个叶结点.图5(c)中,结点F没有左儿子而有右儿子L,故它不是一棵近似满二叉树.

　　二叉树的操作

　　二叉树的常用操作与树的常用操作相似.

　　运算含义

　　Parent(v,T)这是一个求父结点的函数,函数值为树T中结点v的父亲.当v是根结点时,函数值为∧,表示结点v没有父结点.

　　Left_Child(v,T)这是一个求左儿子结点的函数.函数值为树T中结点v的左儿子.当结点v没有左儿子时,函数值为∧.

　　Right_Child(v,T)这是一个求右儿子结点的函数.函数值为树T中结点v的右儿子.当结点v没有右儿子时,函数值为∧.

　　Create(x,Left,Right,T)这是一个建树过程.该函数生成一棵新的二叉树T,T的根结点v的标号为x,v的左右儿子分别为Left和Right.

　　Label(v,T)这时一个求标号的函数,函数值就是结点v的标号.

　　Root(T)这是一个求树根的函数,函数值为树T的根结点.当T是空树时,函数值为∧.

　　MakeNull(T)这是一个过程,它使T成为一棵空树.

　　二叉树的实现

　　我们已经看到,虽然二叉树与树很相似,但它却不是树的特殊情形.在许多情况下,使用二叉树具有结构简单,操作方便的优点.另外我们也看到,在树的左儿子右兄弟表示法中,实际上已将一棵一般的树转化为一棵二叉树.在更一般的情形,我们还可以将果园或森林转化为一棵等价的二叉树.下面我们来讨论几种二叉树的表示方法.

　　二叉树的顺序存储结构

　　此结构是将二叉树的所有结点,按照一定的次序,存储到一片连续的存储单元中.因此,必须将结点排成一个适当的线性序列,使得结点在这个序列中的相应位置能反映出结点之间的逻辑关系.这种结构特别适用于近似满二叉树.

　　在一棵具有n个结点的近似满二叉树中,我们从树根起,自上层到下层,逐层从左到右给所有结点编号,就能得到一个足以反映整个二叉树结构的线性序列,如图6所示.其中每个结点的编号就作为结点的名称.

　　图6近似满二叉树的结点编号

　　因此,我们可以对树的类型作如下说明：

　　TPosition=integer;

　　TreeType=record

　　NodeCount:integer;

　　NodeList:array[1..MaxNodeCount]ofLabelType;

　　end;

　　将数组下标作为结点名称(编号),就可将二叉树中所有结点的标号存储在一维数组中