五、树与二叉树

所谓非线性结构是指在该类结构中至少存在一个数据元素可以有两个或者两个以上的直接前驱（或者直接后继）元素。
通常称树形结构中的一个元素为一个结点，结点之间的关系为分支。

（一）树的基本概念

树的定义

树是由n(n>=0)个结点组成的有穷集合D与在D上关系的集合R构成的结构，记为T。当n=0时，称T为空树。对于任何一棵非空树，有一个特殊结点t,称之为树的根结点；其余结点被分割成m(m>0)个不相交的子集Di，其中每一个子集Di本身又构成一棵树，称之为根结点t的子树。
树的定义是一个递归定义，因为它的任何一棵子树也是树。

在一棵树中，一个结点被定义为其子树根结点的直接前驱结点，而其子树的根结点则是它的直接后继结点。于是，从逻辑上看，树形结构具有以下特点：

任何非空树中有且只有一个结点没有直接前驱结点，这个结点就是树的根结点。
除根结点之外，其余所有结点有且只有一个直接前驱结点。
包括根结点在内，每个结点可以有多个直接后继结点。
树形结构是一个具有递归特征的数据结构。

因此，树形结构中的数据元素之间存在的关系通常是一对多、或者多对一的关系。

人类的家庭关系可以表示成一个树。企事业单位中的行政关系可以表示成一个树形结构。一个算术表达式可以表示成一棵树。在计算机领域，磁盘上信息组织的目录结构是一种树形结构。在计算机网路系统中，域名管理也是按照树形结构进行的。

树的逻辑表示方法

在不同的领域可以采用不同的方式表示树形结构。树的逻辑表示方法多种多样，但不管采用哪种表示方法，都应该能够正确表达树中数据元素之间的层次关系，甚至还要反映子树之间的某种次序关系。下面介绍几种常见的逻辑表示方法。

树形表示法
借助了自然界中一棵倒置的树。用一个圆圈表示一个结点，圆圈里的字母或者符号表示该结点的数据信息，结点之间的关系通过直线表示。尽管没有方向，但隐含着自上而下的方向性。这种方法最为普遍，因为它形象而且直观。
文氏图表示法
也称集合表示法。
凹入表示法
通过列表缩进的方式表示。
嵌套括号表示法
也称广义表表示法。广义表中的一个字母代表一个结点的数据信息，每个根结点作为由子树构成的表的名字放在广义表的前面，每个结点的子树与子树之间用逗号分开。具体表示为：A(B(E,(K,L),F,G),C(H,I(M,N)),X(J))。

基本术语

为叙述方便，在表达树形结构中结点之间关系的时候常常借助人类家庭关系中的称谓。例如，把某个结点子树的根结点称为该结点的孩子结点（child），而该结点就是其孩子结点的双亲结点（parent）。于是，具有同一双亲的各结点之间称为兄弟结点（brother）。以某结点为根结点的子树中的任一结点都被称为该结点的子孙结点，而某结点的祖先结点则被定义为从树的根结点到该结点的分支上经过的所有结点。

结点的度
结点用于的子树数目称为该结点的度。
树的度
树中各结点度的最大值被定义为该树的度。
叶子结点
度为0的结点称为叶子结点或者终端结点，简称叶结点。叶结点没有子孙结点。
分支结点
度不为0的结点称为分支结点或者非终端结点。有的书把除根结点之外的分支结点称为内部结点。
结点的层次
从根结点所在层开始，根结点在第1层，根结点的孩子结点为第2层...。若某结点在第i层，则其孩子结点（若存在的话）在第i+1层。
树的深度
树中结点的最大层次数被定义为数的深度或者高度。
有序树
若树中结点子树的相对次序不能随意变换，或者说改变前后的树表示的不是同一个对象，则称该树为有序树。否则，该树为无序树。后面的内容着重考虑有序树，极少关心无序树，因为无序树总可能转化为有序树加以研究。
森林
m(m>=0)棵不相交的树的集合被称为森林或树林。对树中每个分支结来说，其子树的集合就是一个森林。

树的性质

非空树的结点总数等于树中所有结点的度之和加1
度为k的非空树的第层最多有k^(i-1)个结点（i>=1）
深度为h的k叉树最多有(k^h-1)/(k-1)
k^0+k1+k^2+...+k(h-1) = (k^{h-1)/(k-1)。所以一棵k叉树的结点总数为(k}h-1)/(k-1)时，称该树为满K叉树。
具有n个结点的k叉树的最小深度为[以k为底的log(n(k-1)+1)]

树的基本操作

树的应用非常广泛，有关树的基本操作可以归纳如下：

SETNULL(T) 建立一棵空树T。
ROOT(x) 或 ROOT(T) 求x所在树的根结点，或者求树T的根结点
PARENT(T,x) 求树T中结点x的双亲结点
CHILD(T,x,i) 求树T中结点x的第i个孩子结点
RIGHTSIBLING(T,x) 求树T中结点x右边的兄弟结点
INSERT(T,x,i,S) 把以S为根结点的子树插入到树T中作为结点x的第i棵子树
DELETE(T,x,i) 删除树T中结点x的第i棵子树
TRAVERSE(T) 对一棵树进行遍历，即按照某个次序依次访问树中所有结点，每个结点仅被访问一次，得到一个由所有结点组成的序列。

（二）树的存储结构

多重链表表示法

在这种多重链表中，每个链结点由（一个数据域）和（若干个指针域）组成，其中，每一个指针域指向该结点的一个孩子结点。
由于在一棵树中，不同的结点，其度数不同，每个结点设置的指针域的数目就有不同的考虑。通常可以有下面两种方法。

定长链结点的多重链表表示
这种存储方法取树的度数作为每个链结点的指针域数目。

# define MaxTreeD   100
typeof struct node{
    datatype data;
    struct node *child[MaxTreeD]
}DTREE

不定长链结点的多重链表表示
这种存储方法是每个链结点都取自己的度数作为指针域的数目。
考虑到实际操作，每个链结点中除了数据域与指针域之外，还应该设置一个存储结点度数的域，用来指明该结点的度，即指明该链结点中指针域的个数。

# define MaxTreeD   100
typeof struct node{
    datatype data;
    int degree;
    struct node *child[MaxTreeD]
}DTREE

这种方法较上一种方法存储开销小，但会给某些操作带来不便。

三重链表表示法

对于树来说，比较合适的存储方法是三重该链表表示法。
这种存储方法是对树中每个结点除了数据域之外都设置3个指针域。其中第1个指针域给出该结点的第1个孩子结点所在链结点的地址，第2个指针域给出该结点的双亲结点所在链结点的地址，第3个指针域给出该结点右边第1个兄弟结点所在链结点的地址。如果这三个都不存在，则相应的指针域都为null。

typeof struct node{
    datatype data;
    struct node *child, *parent, *brother;
}DTREE

对树而言，则要给出根结点所在链结点的存储地址，用一个名为T的变量给出根结点的地址，通常称T为入口指针。

（三）二叉树

每一个结点最多只有两棵子树，通常称这种树为二叉树，在二叉树中严格区分结点的左、右孩子，其次序不能随意颠倒；否则，就变成另一棵二叉树，因此，二叉树是有序树。

二叉树的定义

二叉树是n个结点的有穷集合D与D上关系集合R构成的结构。当n=0时，称该二叉树为空二叉树；否则，它便是包含了一个根结点以及两棵不相交的、分别称为左子树与右子树的二叉树。
根据二叉树的定义，二叉树有5种基本形态：1.空二叉树，2.只要一个根结点而无子树的二叉树，3.只有左子树而无右子树的二叉树，4.只有右子树而无左子树的二叉树，5.左右子树均非空的二叉树。

二叉树的基本操作

与上面讨论过树的基本操作相类似，二叉树可以有如下一些基本操作，这里设BT代表一棵二叉树。

INITIAL(BT) 置BT为空二叉树。
ROOT(BT)或ROOT(x) 求二叉树BT的根结点或者求结点x所在二叉树的根结点。若BT是空二叉树或者x不在二叉树上，则该操作返回“空”。
PARENT(BT, x) 求二叉树BT中结点x的双亲结点。若x结点是二叉树BT的根结点或者二叉树BT中不存在x结点，则该操作返回“空”。
LCHILD(BT,x)和RCHILD(BT,x) 分别求二叉树BT中结点x的左孩子和右孩子结点。若结点x为叶结点或者二叉树中不存在结点x，则该操作返回“空”。
LSIBLING(BT,x)和RSIBLING(BT,x) 分别求二叉树BT中结点x的左兄弟结点和右兄弟结点。若结点x为二叉树的根结点，或者二叉树中不存在结点x，或者结点x是其双亲结点的左孩子（右孩子），则该操作返回“空”。
CREATEBT(x, LBT, RBT) 生成一棵以结点x为根，分别以二叉树LBT和RBT为左子树和右子树的二叉树。
LINSERT(BT, x, y)和RINSERT(BT, x, y) 将以结点y为根结点且右子树为空的二叉树分别置为二叉树BT中结点x的左子树和右子树。若结点x有左子树（右子树），则插入后作为结点y的右子树。
LDELETE(BT,x)和RDELETE(BT,x) 分别删除二叉树BT中以结点x为根结点的左子树和右子树。若结点x无左子树或者右子树，则该操作为空操作。
TRAVERSE(BT) 按某种次序依次访问二叉树BT中的各个结点，并且每个结点只被访问一次，得到一个由该二叉树的所有结点组成的序列。
DESTROYBT(BT) 销毁一棵二叉树。该操作删除二叉树BT中的所有结点，并释放它们的存储空间，使BT称为一棵空二叉树。
LAYER(BT,x) 求二叉树中结点x所处的层次。
DEPTH(BT) 求二叉树BT的深度。若二叉树为空，则其深度为0；否则，其深度等于左子树或者右子树中的最大深度加1。

两种特殊形态的二叉树

满二叉树
如果一棵二叉树中的任意一个结点，或者是叶结点，或者有两棵非空子树，而且叶结点都集中在二叉树的最下面一层，这样的二叉树称为满二叉树。
完全二叉树
若二叉树中最多只有最下面两层结点的度可以小于2，并且最下面一层的结点（叶结点）都依次排列在该层最左边的位置上，具有这样特点的二叉树称为完全二叉树。
满二叉树是完全二叉树的一种特例。在一棵二叉树中，若除了最下面一层外，其余各层都是满的，这样的二叉树称为理想平衡树。理想平衡树包括满二叉树和完全二叉树。

二叉树的性质

二叉树具有一些特殊的性质，简单归纳如下：

具有n个结点的非空二叉树有且仅有n-1个分支
非空二叉树的第i层最多有2^(i-1)个结点
深度为h的非空二叉树最多有2^(h)-1个结点
在任意非空二叉树中，若叶结点的数目为n0，度为2的结点数目为n2，则有关系n0=n2+1
具有n(n>0)个结点的完全二叉树的深度h=以2为底的logn+1
若对具有n个结点的完全二叉树的所有结点从1开始按照层次从上到下，每一层从左至右的规则对结点进行编号，则编号为i的结点具有以下性质。
1）若i>1，则编号为i的双亲结点的编号为 i/2；当i=1时，编号为i的结点为二叉树的根结点，没有双亲结点。
2）若2i<=n，则编号为i的结点的左孩子结点的编号为2i；若2i>n，则编号为i的结点无左孩子。
3）若2i+1<=n，则编号为i的结点的右孩子结点的编号为2i+1；若2i+1>n，则编号为i的结点无右孩子。

二叉树与树、树林之间的转换

这里，把一般树作为有序树来处理，这样不至于引起混乱。

树与二叉树的转换
将一般树转换为二叉树可以按一下步骤进行。
1）在所有相邻兄弟结点之间分别加一条连线。
2）对每个分支结点，除了其最左孩子外，删去该结点与其他孩子结点的连线。
3）以根结点为轴心，顺时针旋转45度。
这样，原来的那棵一般树就转换为一棵二叉树。
树林与二叉树的转换
将一棵树林转换为二叉树的过程可以归纳为如下几个步骤。
1）分别将树林中的每棵树转化为二叉树。
2）从最后那棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，直到所有二叉树全部连接，这样得到的二叉树的根结点就是树林中第1棵树的根结点。
二叉树还原为一般树
将一棵由一般树转换成的二叉树还原为树可以按照以下步骤进行。
1）若某结点是其双亲结点的左孩子，则将该结点的右孩子以及当且仅当连续地沿着此右孩子的右子树方向不断地搜索到的所有右孩子，部分别与该结点的双亲结点用虚线连接起来。
2）删去原二叉树中所有双亲结点与其右孩子的连线。
3）将图形规整化，使各结点按层次排列，并且将虚线改成实线。

（四）二叉树的存储结构

树形结构大多采用链式存储结构，而对二叉树来说，有的时候采用顺序存储结构也比较方便。

二叉树的顺序存储结构

二叉树的顺序存储结构是用一组地址连续的存储单元依次存放二叉树的数据元素。根据二叉树的性质六，完全二叉树中结点编号之间的关系可以正确反映出结点之间的逻辑关系。
于是，若将一棵具有n个结点的完全二叉树上所有结点的数据信息，按照该编号顺序地存放在一个一维数组BT[0,..,MaxSize-1]中（即把编号为i的结点的数据信息存放在数组下标为i-1的数组元素中），则数组中每个元素的下标与该元素在完全二叉树中相应结点的编号相对应，这样，数组元素下标之间的关系同样可以反映出二叉树中结点之间的逻辑关系，并称数组BT为该完全二叉树的顺序存储结构。
这样既不浪费存储空间，又可以方便的利用地址计算公式确定结点的位置。
对于完全二叉树（尤其是满二叉树）采用顺序存储结构比较合适，它能够充分利用存储空间。而对于一般二叉树，如果需要虚设很多“虚结点”才能使它成为一棵形式上的完全二叉树，则采用顺序存储结构就会使得许多存储空间存放的是空值，造成空间浪费。另外，由于顺序存储结构过的一些缺陷，会使得二叉树的插入、删除操作很不方便，且效率也比较低。因此，对于二叉来说，更合适的方法是采用链式存储结构。

二叉树的链式存储结构

所谓二叉树的链式存储结构是指采用链表形式来存储一棵二叉树，二叉树中的每一个结点用链表中的一个链结点来存储。通常有两种形式：

二叉链表结构
链表中每一个链结点由3个域组成，除数据域之外，设置两个指针域，分别给出该结点的左孩子和右孩子所在链结点的存储地址。
三叉链表结构
链表中每一个链结点由4个域组成，增加了指向双亲所在链结点的域，即data、lchild、rchild、parent。
在后续的线索二叉树中确定某结点的直接后继结点时，采用三叉链表要比二叉链表方便一些。

后面所涉及到的二叉树的链式存储结构几乎都是指二叉链表结构。二叉链表结构具有灵活、方便的特点，结点的最大数目只受系统最大可用存储空间的限制。一般情况下，二叉链表结构不仅比顺序存储结构节省空间，而且对二叉树实施有关操作也很方便。
可以按如下方法来描述二叉链表结构中链结点的类型。

typeof struct node {
    datatype data;
    struct node *lchide, *rchild;
}BTNode, * BTREE

下面就围绕二叉树的存储结构来讨论几个算法。

（五）二叉树与树的遍历

树的遍历就是指按照一定的规则将树中所有结点的数据信息排列成一个线性序列的过程，并称这一序列为遍历序列。

二叉树的遍历

若以符号D,L,R分别表示访问根结点、遍历根结点的左子树和遍历根结点的右子树3个过程，则二叉树的遍历方式可以有6种，分别是DLR,LDR,LRD,DRL,RDL和RLD。如果限定先左后右，则通常采用前3种遍历方式，即DLR,LDR,LRD,分别称之为前序遍历、中序遍历、后序遍历，得到的遍历序列分别称之为前序序列、中序序列、后序序列。

前序遍历
前序遍历的原则是：若被遍历的二叉树非空，则按如下顺序进行遍历。
1、访问根结点。
2、以前序遍历方式遍历根结点的左子树。
3、以前序遍历方式遍历根结点的右子树。
若二叉树采用二叉链表作为存储结构，则递归算法如此。
中序遍历
中序遍历的原则是：若被遍历的二叉树非空，则按如下顺序进行遍历。
1、以中序遍历的方式遍历根结点的左子树。
2、访问根结点。
3、以中序遍历的方式遍历根结点的右子树。
递归算法如此。
后序遍历
后序遍历的原则是：若被遍历的二叉树非空，则按如下顺序进行遍历。
1、以后序遍历的方式遍历根结点的左子树。
2、以后序遍历的方式遍历根结点的右子树。
3、访问根结点。
递归算法如此。

然而，并非所有的程序设计语言都允许递归，如Fortran语言就没有递归的功能；另外，递归程序虽然简洁，但可读性一般并不好。因此，就存在如何为递归问题设计一个非递归算法的问题。除了某些情况下可以通过程序设计语言的循环语句来解决之外，一般情况下解决这类问题的关键通常是利用一个堆栈结构。
这里以中序遍历和后序遍历为例说明非递归算法，前序遍历与中序遍历很相似。

按层次遍历
按层次遍历又称广度优先遍历方式。这种遍历方式原则很简单：若被遍历的二叉树非空，则先依次访问二叉树第1层的结点，然后再依次访问第2层的结点，...，依次下去，最后依次访问最下面一层的结点。对每一层结点的访问按照从左至右的先后顺序进行。
这里给出二叉树采用二叉链表存储结构时这种遍历方式的非递归算法。

由遍历序列恢复二叉树

已知一棵二叉树的前序序列和中序序列，可以唯一的确定这棵二叉树。例如，前序序列ABCDEFGHI 和中序序列BCAEDGHFI ，得到广义表示为A(B(,C),D(E,F(G(,H),I))).

到此，已经重点讨论了二叉树的各种遍历方法。最后考虑一个问题，那就是，能否不使用堆栈实现对二叉树的遍历？一个简单的方法是二叉树采用三叉链表结构，在遍历过程中可以沿着走过的路径退回到任意一棵子树的根结点并再次向下遍历；二是采用线索二叉树。

二叉树的等价性

这里讨论二叉树的两个重要概念，一个是相似问题，一个是等价性问题。
如果说二叉树T1和二叉树T2是相似的，则是指它们具有相同的拓扑结构，也就是说它们都是空二叉树，要么它们都不空，并且它们的左右子树都分别相似。
如果说二叉树T1和二叉树T2是等价的，则是指它们不仅具有相同的拓扑结构，而且在它们的对应结点中包含相同的数据信息。
这里给出的是判定两棵二叉树是否相似的算法，若相似，算法返回1，否则返回0.

树和树林的遍历

树的遍历

树由根结点和根结点的子树构成，因此，树有前序遍历和后序遍历两种遍历方式。

前序遍历方式
若被遍历的树非空，则
1）访问根结点
2）依次按照前序遍历方式递归地遍历根结点的每一棵子树。
后序遍历方式
若被遍历的树非空，则
1）依次按照后序遍历方式递归地遍历根结点的每一棵子树。
2）访问根结点

树林的遍历

树林的遍历方式有两种。

前序遍历
若被遍历的树林非空，则
1）访问第1棵树的根结点。
2）按照前序遍历方式遍历第1棵树上根结点的子树林。
3）按照前序遍历方式遍历除去第1棵树以后的子树林。
在遍历任何一个子树林的过程中，仍然是递归地先访问子树林中第1棵树的根结点，然后遍历子树林中第1棵树的子树林，最后遍历子树林中去掉第1棵树后的子树林。
中序遍历
若被遍历的树林非空，则
1）按照中序遍历方式遍历第1棵树上根结点的子树林。
2）访问第1棵树的根结点。
3）按照中序遍历方式遍历除去第1棵树以后的子树林。
遍历任何子树林时，仍然是递归地先遍历子树林中第1棵树上根结点的子树林，然后访问子树林的第1棵树的根结点，最后遍历子树林中去掉第1棵树之后的子树林。

基于二叉树遍历操作的基本算法

在以下算法中，假设二叉树都采用二叉链表作为存储结构，并约定，指向根结点的指针用T表示，

（六）线索二叉树

如前面所述，如果按照某种遍历方式对二叉树进行遍历，就可以把二叉树中所有结点排列为一个线性序列。在该序列中，除第1个结点，每个结点有且仅有一个直接前驱结点；除最后那个结点，每个结点有且仅有一个直接后继结点。但是，二叉树中每个结点在这个序列中的直接前驱结点和直接后继结点是什么，二叉树的存储结构中并没有反映，只能在对二叉树遍历的动态过程中得到这些信息。为了保留结点在某种遍历序列中的直接前驱和直接后继结点的位置信息，可以利用二叉树的二叉链表存储结构中的那些空的指针域。这些指向直接前驱结点和直接后继结点的指针被称为线索，加了线索的二叉树被称为线索二叉树。
在线索二叉树中，常用的操作有：确定线索二叉树中某一结点的前驱或者后继结点；将一个新的结点插入到线索二叉树中使之成为某结点的前驱或者后继结点。线索二叉树为二叉树的遍历提供了很多方便，而且不需要设置堆栈。

线索二叉树的构造

一个具有n个结点的二叉树若采用二叉链表存储结构，在2n个指针域中只有n-1个指针域是用来指向结点的孩子，而另外n+1个指针域存放的都是空值。为此，可以利用某结点空的左指针域(lchild)指出该结点在某种遍历序列中的直接前驱结点的位置，利用结点的有指针域(rchild)指出该结点在某种遍历序列中的直接后继结点的位置，对于那些非空的指针域，则仍然存放指向该结点左、右孩子的指针。这样，就得到了一棵线索二叉树。
由于遍历序列可由不同的遍历方法得到，因此，线索树可以有前序线索二叉树、中序线索二叉树和后序线索二叉树之分。把二叉树改造成线索二叉树的过程称为线索化。
画图时，实线表示指针（指向孩子结点），虚线表示线索（指向前驱或者后继结点）。
在设计有关线索二叉树的算法中，如何区别某个结点的指针域内究竟存放的是指针还是线索（因为线索也是一个地址）呢？通常可以采用下面两种方法处理。

每个结点增设两个标志位域lbit和rbit，则有
p->lbit = 0 表示p->lchild为指向前驱的线索，=1 表示p->lchild为指向左孩子的指针；
p->rbit = 0 表示p->rchild为指向前驱的线索，=1 表示p->rchild为指向右孩子的指针；
不改变链结点的构造，仅在作为线索的地址前面加一个负号，即负的地址表示线索，正的地址表示指针。
这两种区别线索与指针的方法各有利弊。前者与后者相比，增加了存储空间的开销，但在对线索二叉树的操作过程中，对地址的处理要简单。
这时，还要少数几个结点的线索仍然悬空，为此，解决的方法是设置一个头结点，其存储地址即为HEAD，数据域可以不存放信息，只是令其左指针域指向二叉树的根结点，右指针域指向自己。这样，二叉树中所有尚无去处的线索都指向头结点。经过如此处理，后面讨论的算法中不必再判断线索是否为空的情况。
采用第1中区分法，则定义线索二叉树的二叉链表结构如下：

class Node{
    constructor(data, lchild, rchild, lbit, rbit){
        this.data = data
        this.lchild = lchild
        this.rchild = rchild
        this.lbit = lbit
        this.rbit = rbit
    }
}

线索二叉树的利用

建立了线索二叉树以后，可以方便地找到指定结点在某种遍历序列中的直接前驱结点或这接后继结点，而不必再对二叉树重新进行遍历。而且无论是递归算法还是非递归算法，都不会涉及到堆栈。

二叉树的线索化

对二叉树的线索化，就是把二叉树的二叉链表存储结构中结点的所有空指针域改造成指向某结点在某种遍历序列中的直接前驱结点或直接后继结点的过程，因此，因此，二叉树的线索化过程只能在对二叉树的遍历过程中进行。
具体算法在此。

线索二叉树的更新

所谓线索二叉树的更新是指在线索二叉树中插入一个结点或者删除一个结点。一般情况下，这些操作有可能破坏原来已有的线索关系，因此，在修改指针的时候，还需要对线索进行相应的修改。一般来说，这个过程花费的代价几乎与重新进行线索化相同。
具体算法在此。

（七）二叉排序树

二叉树结构被广泛用来解决计算机领域中的各类实际问题。例如，在排序、检索、数据库管理系统以及人工智能等许多方面，二叉树提供了强而有效的支持。有人说，当需要完成的功能是插入、删除和检索时，二叉排序树具有比迄今为止研究过的任何数据结构都更好的性能。
二叉排序树可以用来排序，也可以用来查找（或者称检索）。利用二叉排序树可以大大提高查找的时间效率，因此，二叉排序树也称为二叉查找树或者二叉搜索树。

二叉排序树的定义

二叉排序树是一棵二叉树，若根结点的左子树不为空，则左子树中所有结点的值均小于根结点的值；若根结点的右子树不为空，则右子树中所有结点的值均大于或者等于根节点的值。每一棵子树也同样具有上述特性，即二叉排序树中任何一棵子树也是一棵二叉排序树。
这里为了讨论方便，假设了二叉树中每一个结点的值分别为一个无符号十进制整常数。

二叉排序树的建立

设K=(k1, k2, k3, ..., kn)为数据元素序列。从ki开始依次取序列中的元素，每取出一个数据元素ki，按下列原则建立二叉排序树的一个结点。

若二叉排序树为空，则ki就是二叉排序树的根结点。
若二叉排序树非空，则将ki与该二叉排序树的跟结点的值进行比较。若ki小于根结点的值，则将ki插入到根结点的左子树中；否则，将ki插入到根结点的右子树中。

这是一个递归的过程，因为将一个数据元素插入到根结点的左子树或者插入到根结点的右子树，同样需要按照这个原则递归进行。

很容易想到，对于给定的一个数据元素序列，若元素插入到二叉树的次序不同，则所建立的二叉排序树的形式也不同。
在这里看一个建立二叉排序的例子。
按照上述插入算法中，值相同的数据元素插入到结点的右子树中。可以设想如果，这样的数据元素越多，二叉树的深度会变得越大，这将会降低查找操作的效率。一个解决的办法是适当增加二叉树的存储空间开销，即在链结点中增加一个域以指示相同元素发生的频率。当然，如果数据元素集合指示一个更大结构的一部分，则该方法也有问题。此时可以把相同数据元素保留在一个辅助数据结构中，例如一个表或者另一棵二叉排序树中。
数据元素序列K一般不一定是一个按值排序的序列，但将其构造为一棵二叉排序树以后，对该二叉排序树进行中序遍历，得到的中序遍历序列却是一个按值排序的序列。

在二叉排序树中删除结点

这里讨论的在二叉排序树中删除一个结构是指仅删除指定结点，而不是把以结点为根结点的子树删掉。显然，删除指定结点以后的二叉树仍然要保持二叉排序树的性质。

若要删除的结点由变量p指出，其双亲结点由变量q指出，则删除p所指的结点应该从下面4中情况分别考虑。

若被删除结点为叶结点，则删除比较简单，可以直接进行删除（还要将其双亲结点相应的指针域置为null）。
若被删除结点没有左子树（右子树存在），则可以用其右子树的根结点取代被删除结点的位置。
若被删除结点没有右子树（左子树存在），则可以用其左子树的根结点取代被删除结点的位置。
若被删除结点的左右子树均存在，则要找到被删除结点右子树中值最小的结点（不妨假设r指出该结点的位置），并用该结点取代被删除结点的位置。因为由r指出的结点一定没有左子树，所以用其右孩子来取代r所指结点的位置。
这里给出具体的算法。

二叉排序树的查找

从二叉排序树的定义与构造方法不难看到，将一个数据元素序列构造为一棵二叉排序树以后，要在树中查找序列中某个数据元素存在与否效率，比直接在序列中采用顺序比较的效率要高得多。
其查找过程是：
若二叉排序树为空，则查找失败，结束查找，返回信息null；
否则，将要查找的值与二叉排序树根结点的值进行比较，
若相等，则查找成功，结束查找，返回被查到结点的地址；
若不相等，则根据要查找的值与根结点值的大小关系决定是到根结点的左子树还是右子树中继续查找（查找过程同上），直到查找成功或者查找失败为止。
查找过程是一个递归过程。

查找算法这里给出具体算法。
查找长度
在二叉排序树中查找数据信息与给定值相匹配的结点的过程正好走了一条从根结点到该结点的路径，与给定值所进行的比较次数等于该结点所在的层次数。
对于查找算法的优劣性，通常采用平均查找长度的概念来衡量。
采用“逐点插入方法”建立二叉排序树时，若从序列中取得数据元素的次序不同，得到的二叉排序树一定不同。也就是说，具有n个结点的二叉排序树不是唯一的。因而，在不同的二叉排序树中进行查找的平均查找长度与二叉排序树的形态有关。先定义这一术语。
平均查找长度 确定一个元素在树中位置所需要进行的比较次数的期望值。
二叉树的内路径长度 从二叉树根结点到某结点所经过的分支数目定义为该结点的路径长度。二叉树的所有结点的路径长度之和定义为该二叉树的内路径长度IPL。
二叉树的外路径长度 为了分析查找失败时的查找长度，在二叉树中出现空子树时，增加新的空叶结点来代表这些空子树，从而得到一棵扩充后的二叉树。为了与扩充前的二叉树相区别，这些新增的空的叶结点用小方块表示i，称之为外部结点，树中原有的结点称为内部结点。二叉树中所有外部结点的路径长度之和即为此二叉树的外路径长度EPL。
根据二叉树的性质，扩充后的二叉树中若具有n个内部结点，则必然有n+1个外部结点。不难证明，EPL=IPL+2n。
现在分析二叉排序树的查找长度。在n个结点的二叉排序树中，
若对每个数据的查找概率相等，则对每个结点查找成功所需的比较次数就是该结点所在的层次数，即等于该结点的路径长度加1.查找成功的平均查找长度为ASL=(IPL+n)/n。
对于不成功的查找，比较次数等于表示该数据元素所在范围的外部结点的路径长度。因此，查找失败时的平均查找长度为ASL=EPL/n=(IPL+2n)/n。
考虑到在二叉排序树中查找成功与不成功的全部可能性，设对扩充后的二叉树的每个结点（包括内部节点和外部结点）进行查找的概率相等，则平均查找长度为ASL=(IPL+n+EPL)/(n+n+1) =(2IPL+3n)/(2n+1)。
由此可见，要使得二叉排序树具有最小的平均查找长度，应该使内路径长度达到最小。具有最短内路径长度的二叉排序树被称为最佳二叉排序树，可以证明，最佳二叉排序树的平均查找长度为O(以2为底的logn)。
最坏的情况下，二叉排序树退化为一棵单支的二叉树，其平均查找长度为(n+1)/2，是O(n)量级。

（八）平衡二叉树

二叉排序树有一个缺陷，即树的形态事先无法预料，随意性很大，它与二叉树中结点的值以及结点的插入排序有关，得到的往往是一棵很不“平衡”的二叉树。二叉排序树与理想平衡树相差越远，树的深度差就越大，其运算时间也就越长。最坏的情况就是对单链表（对应的二叉排序树为单支二叉树，即退化二叉树）进行运算的时间，从而部分或者全部地丧失了利用二叉排序树组织数据带来的好处。为了克服二叉排序树的这个缺陷，需要在插入和删除结点的同时对二叉树的形态（结构）进行必要的调整，使得二叉排序树始终处于一种平衡状态，始终称为一种平衡二叉树，简称平衡树。当然，它还不是理想平衡树，以为那将使得调整操作更为复杂，是调整带来的好处得不偿失。
平衡二叉树（balanced binary tree 或 height-balanced tree）又称AVL树。它是具有下列性质的树：二叉树中每个结点左右子树的深度之差的绝对值不超过1。把二叉树中每个结点的左子树深度与右子树深度之差定义为该结点的平衡因子，因此，平衡二叉树中每个结点的平衡因子只能是1，0或-1。
虽然平衡树的平衡性比理想平衡树的要差一些，但理论上已经证明，具有n个结点的平衡树的深度在任何情况下都不会比具有相同结点数目的理想平衡树的深度高出45%以上。因此，在平衡树上进行查找操作虽比理想平衡树要慢一些，但通常比在任意生成的二叉排序树中进行查找要快的多，但其时间复杂度的数量级仍为O(以2为底的logn)。
当在一棵平衡二叉树中插入一个新结点时，若插入以后某些结点的左右子树的深度不变，则不会影响这些结点的平衡因子，因而也不会因为这些结点导致不平衡；

若插入以后某些结点的左子树的深度增加1（右子树的深度增加1的情况与之类似），就会影响这些结点的平衡因子，具体又分为以下3种情况：

若插入前一部分结点的左子树深度hL与右子树深度hR相等，即平衡因子为0，则插入后将使平衡因子变为1，仍符合平衡的条件，因此不必对它们进行任何调整。
若插入前一部分结点的hL小于hR，即平衡因子为-1，则插入后将平衡因子变成0，平衡性更加改善，故也不必对它们进行调整。
若插入前一部分结点的hL大于hR，即平衡因子为1，则插入后使得平衡因子变为2，破坏了平衡树的限制条件，因此需要对它们进行调整，使得整棵二叉排序树恢复为平衡树。

若插入以后某些结点的右子树深度增加1，也要分成相应的3中情况讨论：

平衡因子由0变成-1，不必进行调整；
平衡因子由1变成0，也不必进行调整；
由于平衡因子由-1变成-2，必须对其进行相应的调整。

如果在平衡二叉树中插入一个结点以后破坏了其平衡性，则首先要找出最小不平衡子树，然后再调整该子树中的有关结点之间的链接关系，使之成为新的平衡子树。当然，调整以后该子树的二叉排序树性质不能改变，即调整前后得到的二叉排序树的中序序列要完全相同。后面将会看到，最小不平衡子树被调整为平衡子树后，原有的其他不平衡子树无需调整，整个二叉排序树就又称为一棵平衡树。
所谓最小不平衡树是指，以离插入结点最近，并且平衡因子绝对值大于1的结点为根的子树。
为了方便讨论，用A来表示最小不平衡子树的根结点。于是，调整该子树的操作可以归纳为以下4种情况：

LL型调整
LL型调整是对由于在结点A的左L孩子（用B表示）的左L子树上插入结点，使得结点A的平衡因子由1变为2而引起的不平衡所进行的调整操作。
调整的原则是：将结点A的左孩子B向右上旋转，替代结点A成为根结点；将结点A向右下旋转，成为结点B的右子树的根结点，而结点B的原右子树B1则作为结点A的左子树。
此调整过程需要修改3个指针：将原指向结点A的指针修改为指向结点B，将结点B的右指针修改为指向结点A，将结点A的左指针修改为指向结点B的原右子树的根结点B1。另外还需要修改结点A和结点B的平衡因子。
调整前后对应的中序序列相同，即经过调整后仍然保持了二叉排序树的性质不变。
RR型调整
RR型调整是对由于在结点A的右R孩子（用B表示）的右R子树上插入结点，使得结点A的平衡因子由-1变为-2而引起的不平衡所进行的调整操作。
调整的原则是：将结点A的右孩子B向左上旋转，替代结点A成为根结点；将结点A向左下旋转，成为结点B的左子树的根结点，而结点B原左子树B1则作为结点A的右子树。
此调整过程需要修改3个指针：将原指向结点A的指针修改为指向结点B，将结点B的左指针修改为指向结点A，将结点A的右指针修改为指向结点B的原左子树B1的根结点。另外还要修改结点A和结点B的平衡因子。
LR型调整
LR型调整是对由于在结点A的左L孩子（用B表示）的右R子树上插入结点，使得结点A的平衡因子由1变成2引起的不平衡所进行的操作。
调整原则为：将结点A的左孩子的右子树的根结点C提升到结点A的位置；将结点B作为结点C的左子树的根结点，而结点C原来的左子树B1作为结点B的右子树；将结点A作为结点C的右子树的根结点，而结点C原来的右子树作为结点A的左子树。
此调整过程需要修改5个指针：将原指向结点A的指针修改为指向结点C，将C的左指针指向结点B，将C的右指针指向A，将B的右指针指向C原来的左子树B1。
RL型调整
RL型调整是对由于在结点A的右R孩子（用B表示）的左L子树上插入结点，使得结点A的平衡因子由-1变成-2而引起的不平衡所进行的调整操作。
调整原则为：将结点A的右孩子的左子树的根结点C提升到结点A的位置；将结点B作为结点C的右子树的根结点；将结点A作为结点C的左子树，而结点C原来的左子树B1作为结点A的右子树。
此调整过程需要修改5个指针：将原指向结点A的指针修改为指向结点C，将C的左指针指向结点A，将C的右指针指向B，将A的右指针指向C原来的左子树B1。

在二叉排序树的插入和删除操作中采用平衡树的优点是使二叉排序树的结构较好，从而提高了查找操作的时间效率；缺点是使得插入和删除操作复杂化，从而降低了运算速度。这是由于在每次运算中，不仅要进行插入或删除结点，而且要检查是否存在有最小不平衡子树（实验表明，平均每两次插入或者5次删除操作都要出现一次不平衡）；若存在，则需要对最小不平衡子树中的有关指针进行修改。因此平衡树适合于二叉排序树一经建立就很少进行插入和删除操作，而主要是用于查找的应用场合。

（九）哈夫曼树及其应用

哈弗曼树的概念

上面给出过二叉树的路径长度，这里进一步定义带权的路径长度WPL的概念：若设二叉树有m个叶结点，每个叶结点分别赋予一个权值，则二叉树的带权路径长度为WPL=w1l1+w1l2+w3l3+...+wmlm，其中，wi为第i个叶结点被赋予的权值；li为第i个叶结点的路径长度。
用一组权值可以构造出不同带权二叉树，其带权路径长度各不相同。其中二叉树的WPL最小，它就是哈夫曼树，由此可见，带权路径长度最小的二叉树并非满二叉树，也非完全二叉树。
给定一组权值，构造成的具有最小带权路径长度的二叉树称为哈夫曼树（Huffman），又称为最优二叉树。权值越大的叶结点离根结点越近，权值越小的叶结点离根结点越远，这样的二叉树的WPL最小，哈弗曼树就满足这一特性。另外，给定一组权值，构造出的哈弗曼树的形态可能不唯一，但它们的WPL都一样。从形态上可以看到，哈弗曼树中不存在度为1的结点。

构造具有最小WPL的带权二叉树的算法是哈夫曼给出的，因此又称为哈夫曼算法。其基本思想如下：

将给定的权值按照从小到大排列称（w1, w2, ..., wm），并且构造出树林F=(T1, T2, ...,Tm)。此时，其中的每棵树Ti(1<=i<=m)都为左右子树均为空的二叉树，二叉树的根结点的权值为wi。
把F中树根结点的权值最小的两棵二叉树T1和T2合并为一棵新的二叉树T（T的左子树为T1，右子树为T2），并令T的根结点的权值为T1和T2根结点的权值之和，然后将T按其根结点的权值大小依次加入到树林F中。同时，从F中删去T1和T2这两棵二叉树。
重复步骤2，直到构成一棵哈夫曼树。

*哈夫曼编码

哈夫曼树的应用十分广泛。尤其在数据压缩与信息编码领域更是这样。在不同的应用中，赋予叶结点的权值可以有不同的解释：当哈夫曼树应用到信息编码中时，权值可以看成是某个符号出现的频率；当应用到判定过程中，权值可以看成是某一类数据出现的频率；当应用到排序问题时，可以看成是已排好次序而待合并的序列的长度。
应用哈夫曼树较多的是通讯及数据传送中的二进制编码，及哈弗曼编码。目前，用电报传送的字符常常被转换成二进制代码传送。如何使得传送的电文编码总长度最短？利用哈夫曼编码将能达到这一目的。
哈夫曼编码的算法

（十）红黑树

红黑树Red-Black Tree 「RBT」，就是如（八）所讲的平衡二叉树，这是加了红色与黑色的概念。

（十一）B+ 和 B- 树

B-树的基本概念

这种结构是1970由R. Bayer 和 E. MacCreight提出的，是一种平衡的多分树，多用于文件的索引结构。
B-树是一种多级索引结构，B-树结构在数据处理中起着巨大的作用，已经成为数据处理中主要的文件组织形式。它以占用存储空间少，查找效率高的优势在数据库系统的索引技术中占据了重要的地位。

定义一个m阶B-树应为满足下列条件的结构。

每个分支结点最多有m棵子树。
除根结点外，其他每个分支结点至少有m/2棵子树。
根结点至少有两棵子树（除非根结点为叶结点，此时B-树只有一个结点）
所有叶结点都在同一层上，叶结点不包含任何关键字信息（可以把叶结点看成实际上不存在的外部结点，指向这些“叶结点”的指针为空）。
所有分支结点中包含下列信息 n, p0, key1, p1, key1, ..., keyn, pn。其中，n为该结点中关键字值的个数；keyi（1<=i<=n）为该结点的第i个关键字值，并且满足关系keyi<key(i+1)(i=1,2,...,n-1)；pi(0<=i<=n)为指向该结点第i+1棵子树根结点的指针。

实际上，每个结点还包括了n个指向相应记录的指针（即记录的存储位置。考虑到图形的清晰，这里吧这些指针从图中略去了，而实际是存在的），使得每个结点既是索引的索引块，又是基本索引块（能直接给出记录存放地址的索引块）。pi所指的子树中，所有结点的关键字值均小于key(i+1)而大于keyi。
B-树中的结点类型可以按如下定义：

# define M 10   // B-树的最大阶数
typeof struct node {
  int keynum; //本节点中关键字值的个数
  keytype key[M+1];  //本结点的n个关键字，其中key[0]未用
  struct node * ptr[M+1]  //本结点的n+1个指向子树的指针
  rectype * receptor[M+1]  //与本节点的n个关键值对应的记录的存储位置
} * BTree

B-树的基本操作

B-树的查找

B-树是一种平衡查找树，在B-树上进行查找的过程与在二叉排序树中的查找过程类似。
查找过程可以描述为：根据给定的关键字值ki，先在根结点的关键字集合中采用顺序查找方法或者折半查找方法（因为结点中的关键字是按值有序排列的）进行查找。若有k=keyi，则查找成功，根据相应的指针即可取得记录；否则，若ki<keyi(i=1,2,..,n)，则取指针p(i-1)所指结点后重复这个查找过程，直到在某结点中查找成功，或者在查找过程中出现p(i-1)=空（null），查找失败。
可见在B-树中查找记录的过程是一个沿着指针查找结点和在结点的关键字集合中顺序查找记录的交叉过程。
这里给出查找算法。

B-树的插入

B-树的生成是从空树开始，逐个插入关键字值而得到的。
插入规则：在深度为h+1的m阶B-树中插入关键字为k的记录，首先要查到树的第h层，确定k应该插入的结点，然后再进行插入。若插入后该结点中关键字数目不超过m-1，则插入成功。否则，以中间那个关键字值为界把结点一分为二，产生一个新的结点，并把中间关键字插到双亲结点中；若双亲结点也出现上述情况，则需要再次进行分裂；最坏的情况是一直分裂到根结点，以至于B-树的层数增加一层。可见，B-树的插入操作要比查找复杂得多。尽管这样，插入也可以在O(以2为底的logn)的时间内完成。

B-树的删除

在深度为h+1的m阶B-树中删除一个关键字值为k的记录，首先要找到该关键字值所在的结点，然后区别以下不同情况进行具体删除。

若结点为第h层结点，且该结点中关键字数目num>|m/2|-1，则直接在结点中删去该关键字值。
若结点在第h层，其关键字值且num=|m/2|-1，且左（或右）兄弟结点的num>|m/2|-1，则把左（或右）兄弟结点中最大（或最小）关键字值移到其双亲结点中，再把双亲结点中大于（或小于）上移关键字值的关键字值下移到被删关键字值所在的节点中。
若结点为第h层结点，且该结点及其左、右兄弟结点的关键字数目num都等于|m/2|-1，则假设该结点有右兄弟，且其双亲结点中指针pi指向该右兄弟，于是把应删除的关键字值删除以后，把该结点中剩下的关键字值与双亲结点中关键字值keyi合并到pi所指的结点中，然后将keyi从双亲结点中删去。
若所删关键字值所在结点的层数小于h，且为所在结点的第i个关键字k，则以该结点的pi所指子树中的最小关键字x代替keyi；然后根据x原来所在结点，并区别上述3种情况对原来的x进行删除处理。

B-树的插入和删除算法比较复杂。概括地说，在B-树上做插入，首先要为待插入的关键字值k找到插入位置，接着按照顺序表的插入方法把索引项（k,null）插入到该结点的第i个位置上，然后再进行插入之后的循环处理，直到不需要分裂为止。在B-树上进行删除，首先要找到待删除的关键字值k所在的位置，接着按照顺序表的删除方法从相应的叶结点中删除关键字值k所在的索引项，然后再进行删除之后的循环处理，直到不需要合并结点为止。关于B-树的插入和删除的具体算法，待查看相关书籍资料。

B+树的基本概念

B+树是B-树的一种变形。在B-树上，关键字分布在整个B-树上，并且在上一层结点中出现过的关键字不再出现在最底层的结点中，而B+树则不是这样。

定义一个m阶的B+树应满足下列条件：

每个分支结点最多有m棵子树。
除根结点以外，其他每个分支结点至少有|m/2|棵子树。
根结点至少有两棵子树。
有n棵子树的结点中有n个关键字。
叶结点中存放了记录的关键字值以及指向该记录的指针，或者存放基本文件分块之后每一块的最大关键字值和指向该块的指针，叶结点按关键字值大小顺序链接为一个链表。可以把每一个叶结点看成是一个基本索引块。
所有分支结点可看成是索引的索引，结点中仅包含它的各个子结点中最大（或最小）关键字值及指向子结点的指针。

B+树的基本操作

B+树的查找

B+树上有两个头指针：一个是指向B+树的根结点，另一个指向关键字值最小的那个叶结点，所有叶结点链接成一个不定长的线性链表。因此，在B+树中可以采用两种查找方式，一种方式是直接从最小关键字值开始进行查找；另一种方式就是从B+树的根结点开始进行随机查找，这种查找方式与B-树的查找方式相似，只是当分支结点上的关键字值与查找值相等时，查找并不结束，而要继续向下查到叶结点为止。因此，对于B+树，无论查找成工与否，每次查找都走了一条从根结点到某个叶结点的路径。查找的时间效率分析也类似B-树。

B+树的插入

B+树与B-树的插入操作很相似，但总是插在叶结点上。当叶结点中关键字值数num>m时，该结点分裂为两个结点，分别使关键字值的个数为|(m+1)/2|和|(m+1)/2|，并且双亲结点中必须包括这两个结点的最大关键字值。

B+树的删除

对于B+树而言，只是在叶结点中删除关键字值。当叶结点中最大关键字值被删除时，分支结点中的关键字值可以作为“分界关键字值”存在。如果因为删除操作而使得结点中关键字值的数目少于|m/2|时，则要与兄弟结点进行合并，合并过程和B-树的合并过程类似。