⑴若A为根结点，则A为公共祖先；
⑵若A->datadata且root->datadata，root为公共祖先；
⑶若A->datadata且B->datadata，则到左子树查找；
⑷若A->data>root->data且B->data>root->data，则到右子树查找。
具体算法如下：
（简答题）
编写算法，在二叉排序树上找出任意两个不同结点的最近公共祖先。
正确答案
设两个结点分别为A和B，根据题目要求分下面情况讨论：
⑴若A为根结点，则A为公共祖先；
⑵若A->datadata且root->datadata，root为公共祖先；
⑶若A->datadata且B->datadata，则到左子树查找；
⑷若A->data>root->data且B->data>root->data，则到右子树查找。
具体算法如下：
⑴若A为根结点，则A为公共祖先；
⑵若A->datadata且root->datadata，root为公共祖先；
⑶若A->datadata且B->datadata，则到左子树查找；
⑷若A->data>root->data且B->data>root->data，则到右子树查找。
具体算法如下：
答案解析
略
相似试题
（简答题）
编写算法求给定结点在二叉排序树中所在的层数。
（简答题）
编写在以BST为树根指针的二叉搜索树上进行查找值为item的结点的非递归算法，若查找成功则由item带回整个结点的值并返回true，否则返回false。
（填空题）
在一裸二叉排序树上按（）遍历得到的结点序列是一个有序序列。
（填空题）
在一棵二叉排序树上按（）遍历得到的结点序列是一个有序序列。
（单选题）
设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。
（填空题）
在结点数确定的二叉排序树上进行查找的平均查找长度与二叉树的形态有关，最好的情况是二叉排序树为（）树的时候。
（填空题）
在结点数确定的二叉排序树上进行查找的平均查找长度与二叉树的形态有关，最差的情况是二叉排序树为（）树的时候。
（填空题）
在一棵二叉排序树上实施（）遍历后，其关键字序列是一个有序表。
（判断题）
二叉排序树上左子树上所有结点的值均小于它的根结点的值。
