下载掌阅APP，畅读海量书库
立即打开
树结构是以分支关系定义的一种层次结构，应用树结构组织起来的数据，逻辑上都具有明显的层次关系。操作系统中的文件管理系统、网络系统中的域名管理、数据库系统中的索引管理等都使用了树结构来组织和管理数据，本章就来介绍一下树结构的基本知识。
1.树的定义
树（Tree）是由 n （ n ≥0）个节点组成的有限集合。在任意一棵非空树中，
（1）有且仅有一个根（Root）节点。
（2）当 n >1时，其余节点分为 m （ m >0）个互不相交的有限集： T 1 ，T 2 ， …， T m ，其中每一个集合都是一棵树，称为子树（SubTree）。
这种定义似乎有些抽象，可以通过图2-1直观地理解树的概念。
图2-1 树结构示意
图2-1中每个圆圈表示树的一个节点，其中节点A称为树的根节点，节点{B，E，F}{C}{D，G}构成3个互不相交的集合，它们都是根节点A的子树，每一棵子树本身也是树。
2.常见术语
节点的度（Degree）：节点拥有的子树数量称为该节点的度。例如图2-1中节点A的度为3，因为它有3棵子树。
树的度：树中各节点度的最大值称为该树的度。例如图2-1中树的度为3。
叶子节点（Leaf）：度为0的节点称为树的叶子节点。例如图2-1中节点E、F、C、G都是叶子节点。
孩子节点（Child）：一个节点的子树的根节点称为该节点的孩子节点。例如图2-1中节点B、C、D均为节点A的孩子节点。
双亲节点（Parent）：双亲节点与孩子节点对应，如果节点B是节点A的孩子节点，那么节点A称为节点B的双亲节点。例如图2-1中节点A称为节点B、C、D的双亲节点。
兄弟节点（Sibling）：一个双亲节点的孩子节点互为兄弟节点。例如图2-1中节点B、C、D互为兄弟节点。
节点的层次（Level）：从根节点开始，根节点为第1层，根节点的孩子节点为第2层，以此类推。如果某节点位于第 l 层，其孩子节点就在第 l +1层。例如图2-1中节点E、F、G均位于树的第3层。
树的深度（Depth）：树中节点的最大深度称为树的深度。例如图2-1中树的深度为3。
森林（Forest）： m （ m ≥0）棵互不相交的树的集合称为森林。
3.树的性质
性质1：非空树的节点总数等于树中所有节点的度之和加1。
性质2：度为 k 的非空树的第 i 层最多有 k i -1 个节点（ i ≥1）。
性质3：深度为 h 的 k 叉树最多有 k h -1/（ k -1）个节点。
性质4：具有
n
个节点的
k
叉树的最小深度为
。
以上是树结构的一些基本特性，在此不做证明，有兴趣的读者可查阅其他书目了解证明过程。
二叉树是一种特殊形式的树结构，前面所讲的树的特性及术语同样适用于二叉树。
1.二叉树的定义
二叉树（Binary Tree）或者为空，或者由一个根节点加上根节点的左子树和右子树组成，要求左子树和右子树互不相交，且同为二叉树。很显然，这个定义是递归形式的。图2-2为二叉树的结构示意。
图2-2 二叉树的结构示意
二叉树中的每个节点至多有两个孩子节点，其中左边的孩子节点称为左孩子，右边的孩子节点称为右孩子。
2.满二叉树与完全二叉树
如果二叉树中的任意节点都是叶子节点或有两棵子树，同时叶子节点都位于二叉树的底层，则称其为满二叉树，图2-3所示为满二叉树。
若二叉树中最多只有最下面两层节点的度小于2，并且底层节点（叶子节点）依次排列在该层最左边的位置上，则称其为完全二叉树，图2-4所示为完全二叉树。
图2-3 满二叉树
图2-4 完全二叉树
由于二叉树的结构具有特殊性，因此有一些重要的性质需要大家掌握。
性质1：在二叉树中第 i 层上至多有2 i -1 个节点（ i ≥1）。
性质2：深度为 k 的二叉树至多有2 k -1个节点（ k ≥1）。
性质3：对于任何一棵二叉树，如果其叶子节点数为 n 0 ，度为2的节点数为 n 2 ，则 n 0 = n 2 +1。
性质4：具有
n
个节点的完全二叉树的深度为
+1。
3.二叉树的存储形式
二叉树一般采用多重链表的形式存储，直观地讲就是将二叉树的各个节点用链表节点的形式连接在一起。这样通过特定算法可以对二叉树中的节点进行操作。图2-5所示为多重链表存储的二叉树。每个节点都包含3个域，除一个数据域用来存放节点数据外，还包含两个指针域，用来指向其左右两个孩子节点。当该节点没有孩子节点或者缺少某个孩子节点时，相应的指针域将被置为null。
图2-5 多重链表存储的二叉树
二叉树节点包含3个域，其中leftChild和rightChild为指针域，指向该节点的左孩子和右孩子。data是数据域，用来存放该节点中包含的数据。二叉树节点的结构如图2-6所示。
图2-6 二叉树节点的结构
二叉树的节点可定义如下。
上述代码定义了一个二叉树的节点类型BinaryTreeNode，其中包含3个数据成员：data是一个整型变量（也可以是其他类型的变量），用来存放节点中的数据；leftChild是BinaryTreeNode类型变量，用来指向该节点的左孩子；rightChild也是BinaryTreeNode类型变量，用来指向该节点的右孩子。此外还定义了一个构造函数，用来初始化二叉树节点的实例。构造函数的参数指定了该节点中数据域的值data，同时在构造函数中要将leftChild和rightChild两个变量置为null，表示当前节点没有左孩子和右孩子。
对于一棵二叉树而言，只要得到了它的根节点指针（引用），就可以通过链表结构访问到二叉树中的每一个节点。所以在定义二叉树类时，通常只需要保存二叉树的根节点，而不需要记录二叉树中每一个节点的信息。可以通过下面这段代码定义一个二叉树类。
所谓二叉树的遍历（Traversing Binary Tree）就是通过某种方法将二叉树中的每个节点都访问一次，并且只访问一次。在实际应用中，经常需要按照一定的顺序逐一访问二叉树中的节点，并对其中的某些节点进行处理，所以二叉树的遍历操作是二叉树应用的基础。
二叉树的遍历分为两种：一种是基于深度优先搜索的遍历，它是利用二叉树结构的递归特性设计的。人们熟悉的先序遍历、中序遍历、后序遍历都属于这种遍历。另一种是按层次遍历二叉树，它是利用二叉树的层次结构，并借助队列设计的。
1.基于深度优先搜索的遍历
从二叉树的定义可知，一棵二叉树由根节点、左子树和右子树3部分构成，因此只要完整地遍历了这3部分，就等同于遍历了整棵二叉树。二叉树的根节点可以通过root指针直接遍历，但是如何遍历左子树和右子树呢？我们可以把根节点的左子树和右子树看成两棵独立的二叉树，以同样的方式来遍历它们。显然这是一种递归形式的遍历算法，也是一种基于深度优先搜索的遍历算法。
基于深度优先搜索的遍历算法一般有3种：先序遍历（DLR）、中序遍历（LDR）和后序遍历（LRD）。其中D表示根节点，L表示左子树，R表示右子树。因为二叉树结构本身就是一种递归的结构，所以这3种遍历算法也都是以递归形式定义的，下面具体介绍一下。
（1）先序遍历（DLR）。
◎ 访问根节点。
◎ 先序遍历根节点的左子树。
◎ 先序遍历根节点的右子树。
其Java代码描述如下。
（2）中序遍历（LDR）。
◎ 中序遍历根节点的左子树。
◎ 访问根节点。
◎ 中序遍历根节点的右子树。
其Java代码描述如下。
（3）后序遍历（LRD）。
◎ 后序遍历根节点的左子树。
◎ 后序遍历根节点的右子树。
◎ 访问根节点。
其Java代码描述如下。
在上述代码中，访问根节点的函数visit（）可依据实际情况自行定义，它可以是读取节点中数据的操作，也可以是其他复杂的操作。
假设现在内存中已存在一棵二叉树，其形态如图2-7所示。
图2-7 二叉树示意
该二叉树的先序遍历序列为{2，3，5，0，6，7}；中序遍历序列为{5，3，0，2，7，6}；后序遍历序列为{5，0，3，7，6，2}。
2.按层次遍历
按层次遍历二叉树是一种基于广度优先搜索思想的二叉树遍历算法。不同于前面讲过的先序、中序和后序遍历，按层次遍历二叉树针对二叉树的每一层进行。若二叉树非空，则先访问二叉树的第1层节点，再依次访问第2层、第3层节点，直到遍历完二叉树底层节点。对二叉树中每一层节点的访问都按照从左至右的顺序进行。
在遍历时，需要一个队列作为辅助工具，具体步骤如下。
（1）将二叉树的根节点指针（引用）入队列。
（2）将队首的指针元素出队列并利用这个指针访问该节点，然后依次将该节点的左孩子（如果存在）和右孩子（如果存在）的指针入队列。
（3）重复（2）的操作，直到队列为空。
按照上述步骤实现的对二叉树的按层次遍历可以用下面的代码来实现。
在函数LayerOrderTraverse（）中首先创建一个队列用来保存二叉树节点的指针。方便起见，该队列使用Java容器类LinkedList的泛型类实现，这样可以指定队列中的每个数据元素都是BinaryTreeNode类型的。当然也可以采用第1章中介绍的MyQueue类实现这个辅助队列，但在使用之前需要对MyQueue类加以改造，使其每个队列节点的数据域都是BinaryTreeNode类型的。
接下来就是重复执行步骤（2）、步骤（3），只要队列queue不为null，就不断地取出队头元素并访问该节点，然后将该节点的左孩子和右孩子依次入队列（如果有左孩子或右孩子），直到队列为null。
按照上述算法，实现对图2-7所示的二叉树的按层次遍历，访问节点的次序及队列状态的变化如表2-1所示。
表2-1 访问节点的次序及队列状态变化
所以图2-7所示的二叉树按层次遍历的序列为{2，3，6，5，0，7}。
前面已经详细介绍了二叉树的遍历方法，但是这一切都要以存在一棵二叉树为基础。本节我们就来研究如何创建一棵二叉树。
最常见的创建二叉树的方式是利用二叉树遍历的思想，在遍历过程中生成二叉树的节点，进而建立起整棵二叉树。需要按照一定的顺序生成二叉树的节点，同时建立起双亲节点与孩子节点之间的关系。一般情况下，可以按照先序序列建立一棵二叉树，例如，图2-7所示二叉树的先序序列为{2，3，5，0，6，7}。如果按先序序列生成这棵二叉树，那么生成节点的顺序也应该是2、3、5、0、6、7。
按照先序序列创建一棵二叉树的算法实现如下。
函数CreateBiTree（）可以按照先序序列创建一棵二叉树。该函数的参数是一个LinkedList<Integer>类型的对象，它是一个链表，保存了二叉树中每个节点的元素（这里是整型元素）值，用来初始化二叉树节点，同时这些元素在nodeList中以先序序列的方式排列并指定了该二叉树双亲节点与孩子节点之间的关系。
函数CreateBiTree（）先从nodeList中取出第1个元素，如果该元素不为null，则创建一个BinaryTreeNode类型的节点node，并将取出的元素作为node中的数据元素，再递归地创建以node节点为根节点的二叉树的左子树和右子树。如果从nodeList中取出的第1个元素为null，则说明本层递归调用中要创建的二叉树（或二叉树的某棵子树）为空，直接返回null即可。
如果使用函数CreateBiTree（）创建一棵如图2-7所示的二叉树，那么参数nodeList指定的二叉树节点元素序列应为{2，3，5，null，null，0，null，null，6，7，null，null，null}。这个序列实际上就是在原有的先序序列上加上null作为递归的结束标志。当创建叶子节点时，由于叶子节点的左、右子树都为空，因此要连续保存两个null在该序列中。
至此我们已经详细地介绍了二叉树的定义，二叉树的先序、中序、后序遍历，二叉树的按层次遍历以及如何创建一棵二叉树。下面给出完整的二叉树类定义和测试程序供读者参考。
在上面的代码中，将创建二叉树的函数CreateBiTree（）以及二叉树遍历函数PreOrderTraverse（）、InOrderTraverse（）、PostOrderTraverse（）都进行了封装，使得它们对外提供的接口可以不以二叉树的根节点作为返回值或参数。这样二叉树根节点（BinaryTreeNode root）可以作为私有成员被隐藏起来，代码结构也更加符合面向对象的程序设计思想。
在测试程序中，首先调用CreateBinaryTree（）函数创建一棵如图2-7所示的二叉树，然后分别调用不同遍历方法对该二叉树进行遍历，并将遍历的结果输出。运行结果如图2-8所示。
图2-8 运行结果
二叉排序树也称二叉查找树，是一种特殊形式的二叉树。所谓二叉排序树，它或者是一棵空树，或者是具有下列性质的二叉树。
（1）若它的左子树不为空，则左子树上所有节点的值均小于根节点的值。
（2）若它的右子树不为空，则右子树上所有节点的值均大于根节点的值。
（3）二叉排序树的左右子树都是二叉排序树。
图2-9所示是一棵二叉排序树。
图2-9 二叉排序树示意
如图2-9所示，二叉排序树以根节点为界，将二叉树的节点分为两部分，左子树中节点的值均小于根节点的值；右子树中节点的值均大于根节点的值。左子树和右子树也满足同样的规律，即以子树的根节点为界，将子树的节点分为“左小右大”的两部分。这样就构成了二叉排序树的递归结构。
由于二叉排序树具有以上特性，所以在二叉排序树中查找元素时，首先将给定的关键字与根节点的关键字比较，若相等则查找成功，否则将根据给定的关键字与根节点的关键字之间的大小关系，在左子树或右子树中继续查找。例如，在图2-9所示的二叉排序树中搜索key=8的步骤如下。
（1）将key与根节点关键字10比较，因为8<10，所以在该节点的左子树中继续搜索。
（2）将key与关键字5比较，因为8>5，所以在该节点的右子树中继续搜索。
（3）将key与关键字8比较，相等，查找成功，返回该节点的指针。
当然也可能存在在二叉排序树中查找不到给定的关键字的情况，例如在图2-9所示的二叉排序树中搜索key=11，搜索步骤如下。
（1）将key与根节点关键字10比较，因为11>10，所以在该节点的右子树中继续搜索。
（2）将key与关键字20比较，因为11<20，所以在该节点的左子树中继续搜索。
（3）将key与关键字12比较，因为11<12，所以在该节点的左子树中继续搜索。
（4）因为节点12的左子树为null，所以查找失败，返回null。
图2-10分别展示了上述搜索key=8和key=11的情形。
图2-10 搜索兲键字key=8和兲键字key=11的情形
除了在二叉排序树中查找节点，还可以向二叉排序树中插入节点。因为二叉排序树主要用作动态查找表，也就是表结构本身可在查找的过程中动态生成，所以插入节点的操作通常在查找不成功时进行，而且新插入的节点一定是查找路径上最后一个节点的左孩子或右孩子，插入新的节点后该二叉树仍为二叉排序树。例如在图2-9所示的二叉排序树中查找key=11会失败，此时就需要向该二叉排序树中插入节点11。插入新节点后，该二叉排序树的形态如图2-11所示。
图2-11 插入节点11后二叉排序树的形态
作为动态查找表，二叉排序树中的节点可以删除。因为删除节点后仍要保持二叉排序树的结构，所以删除节点的操作比其他操作要复杂一些，需要分以下3种情况讨论。
（1）删除的节点为P，并且P是二叉排序树的叶子节点，删除叶子节点后不会破坏整棵二叉排序树的结构，直接删除即可（修改该叶子节点双亲节点的指针域），如图2-12所示。
图2-12 删除的P节点为叶子节点
（2）要删除的节点为P，其双亲节点为Q，且P节点只有左子树P L 或者右子树P R ，则删除P节点后，P L 或P R 将取代P的位置，成为Q的左子树或右子树，如图2-13所示。
图2-13 删除的P节点只有左子树P L 或者右子树P R
（3）要删除的节点为P，其双亲节点为Q，且P节点既有左子树P L 又有右子树P R ，则处理起来比较复杂，图2-14所示为二叉排序树的初始状态。
图2-14 二叉排序树的初始状态
为了更加清晰地展示删除P节点的过程，这里将P节点的左子树P L 展开。假设P L 中除了根节点R还包含R的左子树R L 以及R的右子树R R ，而R R 的根节点为S，S的左子树为S L ，且S没有右子树，也就是说节点S是R的右子树中最大的节点。中序遍历该二叉排序树，可得到遍历序列{R L ，R，S L ，S，P，P R ，Q，…}，该序列从小到大排列。上述假设不失一般性，具有普遍意义。
删除节点P有两种方法。第1种方法是将P的右子树P R 变为S的右子树，然后将P的左子树P L 变为Q的左子树。删除节点P后二叉排序树的形态如图2-15所示。
图2-15 用第1种方法删除P节点后二叉排序树的形态
中序遍历图2-16所示的二叉排序树，可得到遍历序列{R L ，R，S L ，S，P R ，Q，…}。可以看到该中序遍历序列与删除P节点之前的中序遍历序列只差一个P节点，说明删除P节点后该二叉树仍是一棵二叉排序树（节点仍然按值有序）。
第2种方法是用P节点在中序遍历序列中的直接前驱，即S节点，代替P节点。这样S节点就从原来的位置上被删除，S节点的左子树S L （如果存在）则直接作为R节点的右子树。删除P节点后二叉排序树的形态如图2-16所示。
图2-16 用第2种方法删除P节点后二叉排序树的状态
中序遍历图2-16所示的二叉排序树，可得到遍历序列{R L ，R，S L ，S，P R ，Q，…}。这个中序遍历序列同图2-15的中序遍历序列完全一致，说明删除节点P后该二叉树仍是一棵二叉排序树。
在一棵具有 n 个节点的二叉排序树中随机查找一个节点的时间复杂度为 O （log 2 n ）。实践证明，二叉排序树的查找效率与二叉排序树的形态密切相关。如果在创建二叉排序树时插入的关键字是按值有序的，则该二叉排序树就会退化为单枝树。例如插入的节点序列为{1，2，3，4，5}，那么生成的二叉排序树如图2-17所示。
图2-17 退化为单枝树的二叉排序树
在图2-17所示的二叉排序树中查找元素相当于在一个线性序列中顺序查找，时间复杂度为 O （ n ），体现不出二叉排序树的优势。所以最好的情况是二叉排序树完全处于平衡状态，如图2-18所示。此时，二叉排序树的形态与折半查找的判定树相同，平均查找长度与log 2 n 成正比。
图2-18 二叉排序树完全处于平衡状态
为了使二叉排序树始终处于尽可能平衡的状态，人们发明了AVL树。AVL树也称平衡二叉树，它是一种具有自平衡功能的二叉排序树。
AVL树或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是AVL树；左子树和右子树的深度差的绝对值不超过1。
如果将二叉树上节点的平衡因子BF（Balance Factor）定义为该节点的左子树的深度减去右子树的深度，则AVL树的平衡因子只可能是-1、0或1。在AVL树中插入或删除节点后，它可能处于一种不平衡的状态（BF的绝对值大于1），此时就会通过一次或多次AVL旋转来重新实现平衡。
因为AVL树可通过旋转实现自平衡，所以AVL树上任何节点的左、右子树深度之差都不会超过1，AVL树的深度和log 2 n 是相同数量级的（ n 为AVL树中节点的数量）。因此从AVL树查找一个节点的时间复杂度为 O （log 2 n ）。
案例2-1：计算二叉树的深度
编写一个程序，计算二叉树的深度。
本题难度 ：★★
题目分析 ：
在二叉树中，除根节点外，左子树和右子树也必须是二叉树，所以二叉树具有递归特性。在计算二叉树的深度时，依然可以利用这种递归特性，先计算根节点左子树的深度，再计算根节点右子树的深度，然后比较两值并将其中的较大值加1，也就是加上当前根节点这一层，作为二叉树的深度。在计算左子树和右子树的深度时，使用的方法与计算整棵二叉树深度的方法完全相同，只是计算的规模缩小了。
下面给出计算二叉树深度的Java代码描述。
下面是一段测试程序，用来计算如图2-7所示的二叉树深度。
在main（）函数中创建了一棵如图2-7所示的二叉树，然后调用BinaryTree类的getBinaryTreeDepth（）函数计算该二叉树的深度，并将计算结果输出到屏幕上。在getBinaryTreeDepth（）函数中会直接调用getBinaryTreeDepth（root）计算以root为根节点的二叉树深度，这里为了更加符合面向对象的设计思想，将getBinaryTreeDepth（BinaryTreeNode root）函数做了一层封装。
运行结果如图2-19所示。
图2-19 运行结果
本题完整的代码及测试程序可从“微信公众号＠算法匠人→匠人作品→《算法大爆炸》全书源代码资源→2-1”中获取。
案例2-2：计算二叉树中叶子节点的数量
编写一个算法，计算二叉树中叶子节点的数量。
本题难度 ：★★
题目分析 ：
本题可以参照上一题的解法，利用二叉树本身的递归特性来求解。计算二叉树叶子节点的数量，其实就是计算二叉树根节点左子树和右子树的叶子节点的数量之和，而根节点的左子树和右子树本身也是二叉树，所以计算它们的叶子节点数量的方法与上述方法相同，这样就找到了该问题的递归结构。如果该二叉树为null，则叶子节点的数量为0；如果该二叉树只包含一个根节点，则它的根节点就是叶子节点，因此叶子节点的数量为1。这两个条件构成了递归的出口，即递归的结束条件。
下面给出计算二叉树叶子节点数量的Java代码描述。
在上述代码中，将getBinaryTreeLeavesNumber（BinaryTreeNode root）函数进行了一层封装，在getBinaryTreeLeavesNumber（）函数中直接调用带参数的getBinaryTreeLeavesNumber（BinaryTreeNode root）函数。root是一个private访问权限的成员变量，该变量对外不可被访问，这样更加符合面向对象的程序设计思想。
除了上面的解法，本题还可以通过遍历二叉树计算叶子节点的数量。在遍历二叉树时可以访问到二叉树中的每一个节点，所以可以判断当前访问到的节点是否为叶子节点，如果该节点是叶子节点，就将累加器变量count的值加1。当遍历完整棵二叉树后，count记录下的值即为该二叉树中叶子节点的数量。
该算法的Java代码描述如下。
在上面的代码中，累加器变量count是一个整型的成员变量，在递归地调用函数countBinaryTreeLeavesNumberByTraversing（root）遍历二叉树时，不管处于递归的哪一层，都可以直接修改累加器count的值。因为count是private访问权限的成员变量，所以这里将函数countBinaryTreeLeavesNumberByTraversing（BinaryTreeNode root）进行了一次封装，在函数countBinaryTreeLeavesNumberByTraversing（）中传递的参数root，以及返回的叶子节点数量count都是private成员变量，这样更加符合面向对象的程序设计思想。
下面是一段测试程序，用来计算如图2-7所示的二叉树中叶子节点的数量。
运行结果如图2-20所示。
图2-20 运行结果
本题完整的代码及测试程序可从“微信公众号＠算法匠人→匠人作品→《算法大爆炸》全书源代码资源→2-2”中获取。
案例2-3：二叉排序树的最低公共祖先问题
已知存在一棵二叉排序树，其中保存的节点值均为正整数。实现一个函数：
该函数的功能是在这棵二叉排序树中寻找节点值value1和节点值value2的最低公共祖先，该函数的返回值是最低公共祖先节点的值。如图2-21所示，若value1=5，value2=9，那么它们的最低公共祖先是节点8。
图2-21 二叉排序树
本题难度 ：★★★
题目分析 ：
仔细观察图2-21不难发现一个规律：在二叉排序树中，value1和value2的最低公共祖先的值介于value1和value2之间。例如5和9的公共祖先有8和10，那么其最低公共祖先是介于5和9之间的8；再例如1和5的公共祖先有3、8、10，那么其最低公共祖先是介于1和5之间的3。这个规律是由二叉排序树的基本特性决定的，在二叉排序树中，如果两个节点分别位于根节点的左子树和右子树，那么根节点必然是它们的最低公共祖先，而其他公共祖先的值要么同时大于这两个节点的值，要么同时小于这两个节点的值。
由此可得出解决此题的算法：从二叉排序树的根节点出发，当访问的节点大于给定的两个节点时，沿左子树前进；当访问的节点小于给定的两个节点时，沿右子树前进；第1次访问到的介于两个节点值之间的那个节点即是它们的最低公共祖先节点。
其实这个算法并不完善，还需要对一些细节进行修正。这个算法适用的前提是给定的两个节点分别位于二叉排序树中某个根节点的左右子树上。例如，图2-21中的节点5和节点9分别位于以节点8为根节点的左右子树上，这两个节点并不存在祖先和子孙的关系。如果给定的两个节点本身存在祖先和子孙的关系，那么它们的最低公共祖先就不能按照上面的算法求得了。如果按照上述算法寻找，则寻找的步骤如图2-22所示。
图2-22 寻找3和5的最低公共祖先
步骤（1）：因为10同时大于3和5，所以沿左子树前进。
步骤（2）：因为8同时大于3和5，所以沿左子树前进。此时访问到节点3，并没有找到预期的介于3和5之间的节点，所以查找失败。
所以，假设给定的两个节点分别为a和b，并且a是b的祖先，那么节点a和b的最低公共祖先就是a的父节点，因为a的父节点一定是b的祖先，同时该节点必然是a和b的最低公共祖先。例如节点3和节点5的最低公共祖先就是节点8。
另外，如果value1或value2中的一个是根节点，那么是不存在最低公共祖先的，因为根节点没有祖先，所以也应把这种情况考虑进去。
该算法的Java代码描述如下。
需要注意的是，上述算法适用的前提是value1和value2在二叉排序树中真实存在。该算法的核心思想是在二叉排序树中寻找介于value1和value2之间的值，如果value1或value2在二叉排序树中不存在，那么得到的结果是没有意义的。更加完善的做法是预先判断value1和value2是否在二叉排序树中。
下面给出本题的测试程序。
在main（）函数中首先创建了一棵形如图2-21的二叉排序树，然后分别计算节点1、节点9，节点11、节点12，节点8、节点10的最低公共祖先。运行结果如图2-23所示。
图2-23 运行结果
如图2-23所示，节点1、节点9的最低公共祖先是节点8；节点11、节点12的最低公共祖先是节点10；节点8、节点10没有最低公共祖先，因此返回-1。