计算机科学
首页
学历类考试
大学
计算机科学
简答题
编写算法,在二叉排序树上找出任意两个不同结点的最近公共祖先。
正确答案
设两个结点分别为A和B,根据题目要求分下面情况讨论:
⑴若A为根结点,则A为公共祖先;
⑵若A->datadata且root->datadata,root为公共祖先;
⑶若A->datadata且B->datadata,则到左子树查找;
⑷若A->data>root->data且B->data>root->data,则到右子树查找。
具体算法如下:
答案解析
略
分享
语音搜题
拍照搜题
打赏