《编写算法在二叉排序树上找出任意两个不同结点的最近公共祖先》由会员分享，可在线阅读，更多相关《编写算法在二叉排序树上找出任意两个不同结点的最近公共祖先（3页珍藏版）》请在金锄头文库上搜索。
1、#iiiclude#iiicludetvpedef stmct nodeint data;node *lcliild5*rchild;Bitree;Bitree *Inseil(Bitree *S,Bitiee *T) 将 从读取的数据插入二叉排序树中Bitree *p;P=T；while(l)if(S-datadata&p-lcluld=NULL)p-lcluld=S; break;elseif(S-datadata&plchild!=NULL) p=p-lcluld;elseif(S-datap-data&prcluld=NULL) p-rcluld=S;break;elseif(S-da
2、tap-data&prcluld!=NULL) p=p-rcluld;return T;Bitree *Creatsort_bitreeQ建立二叉排序树Bitree *T,*S;int a;T=NULL;pmitf(”建立二叉排序树，并以0结 束!n”)；scanff%dj&a);while(a!=0)S=(Bitree *)malloc(sizeof(Bitree); S-data=a;S-lcluld=S-rchild=NULL;if(T=NULL)T=S；elseT=Insert(SqT); scanff%d”,&a);return T;Bitiee *Searchtree(Bitree
3、 *Tjnt a.iiit b)/查找结点a与b的最近公共祖先结点Bitiee *p,*pre;p=pre=T; while(p!=NULL) if(adata&b data) pe=p;p=p lcluld;else if(ap-data&bp-data) pe=p;p=p rchild;elseif(adata&b p-data)|(ap-data&b data) 结点a与b中，一个结点小于 它们的最近公共祖先结点，另一个大于公共祖先结点 return p;elseif(a=p-data| |b=p-data)/结点a与b中，其中一结点是另一结点的 后代return pre;voidBit
4、iee *T、*q;mt a.b;T=CreatsoiVbitreeQ; pnntf(请输入两个结点:n”); scanf(”d%d；&久&b); q=Seaichtiee(T,a5b);pruitfC1结点d与结点d的最近公共 祖先结点是 %d ?n,a,b,q-data);建立二叉排序贰并如结束？50 34 89 23 42 63 95 36 75 92 0 请输入两个结点：23 36Piess any key to continue建立二叉排序树笄以0结束？50 34 89 23 42 63 95 36 75 92 0请输入两个结点：42 92结点42耳结点92的最近令共祖先结点敷聊 P
5、ress any key to continue.建立二叉排序树笄以0结束？50 34 89 23 42 63 95 36 75 92 0请输入两个结点：63 75结加3耳结点?5的最近公共祖先结点敷9? Press any key to continue.题目：编写算法，在二叉排序树上找出任意两个不同结点的最近公共祖先。 问题分析：本程序要求实现在一棵二叉排序树上查找任意两不同结点的最近公共祖先结点， 为实现上述功能，需要解决的关键问题是：创建一棵二叉排序树及查找两个不同结点的最近 公共祖先结点过程。概要设计：创建二叉排序树时，首先建一棵空二叉排序树，然后逐个读入元素，每读入一个元素, 就建
6、立一个新的结点，并将该结点插入到当前已生成的二叉排序树中，最终生成一棵二叉排 序树。查找两个不同结点的最近公共结点时，分两种情况：第一种是该两个不同结点中一个大 于某个结点S,另一个小于结点S,那么该结点S即是最近公共结点；另一种是该两个不同 结点中，一个结点a是另一个结点b的后代，那么它们的最近公共结点是结点b的父结点。 详细设计：创建二叉排序树，首先建立一棵空二叉排序树（T=NULL）,然后依次从键盘读取元素, 并插入二叉排序树中，直至最终生成一棵二叉排序树为止。在将关键字为23的结点s插入 到二叉排序树中时，具体过程如下：若二叉排序树为空，则结点s为二叉排序树的根。若二叉排序树非空，则将
7、23与二叉排序树的根进行比较，如果23的值小于根结点的 值，则将23插入左子树：如果23的值大于根结点，则将23插入右子树。查找最近公共祖先结点时，将结点a与b的值与二叉排序树根结点的值进行比较，并 记录该根结点的父结点。如果结点a、匕中，一个结点的值大于根结点，另一个小于根结点, 则该根结点即是最近公共祖先结点；如果结点a、b中有一个结点的值等于该根结点，则该 根结点的父结点即是最近公共祖先结点。调试分析及小结：错误及分析：运行程序键盘输入50 34 89 23 42 63 95 36 75 92 0,输入两个不同结点：63 75后， 程序无法继续执行。由于结点75是结点63的孩子结点，但在
8、查找函数中并没有考虑到这种 特殊情况，因此程序执行出错，原程序代码如下：Bitree *Seaichtree(Bitree *T,mt a,int b) 查找结点a与b的最近公共祖先结点Bitree *pie;P=T；while(p !=NULL)if(adata&b data)pre=p； p=p-lcliild;else if(ap-data&bp-data)pre=p;p=p icluld;else if(adata&bp-data)|(ap-data&bdata)return p;如上程序，因为没考虑到特殊情况，故Searchtree()函数无法返回值，导致程序无法继续执 行。改进后代码：Bitree *Seaichtree(Bitree *T,mt a,int b) 查找结点a与b的最近公共祖先结点Bitree *p,*pre;p=pre=T;while(p !=NULL)if(adata&b data)pre=p;p=p-lcliild;else if(ap-data&bp-data)pre=p;p=p icluld;else if(adata&bp-data)|(ap-data&bdata)return p;else if(a=p-data|b=p-data)return pre;
