《编写算法在二叉排序树上找出任意两个不同节点的最近公共祖先》由会员分享，可在线阅读，更多相关《编写算法在二叉排序树上找出任意两个不同节点的最近公共祖先（3页珍藏版）》请在金锄头文库上搜索。
1、源代码：#include stdio.h#include stdlib.htypedef struct nodeint data;struct node *lchild,*rchild;Bit;Bit *InBitree(Bit *S,Bit *T) /将数据插入一个二叉排序树中Bit *p;p=T;while(1)if(S-datadata&p-lchild=NULL) p-lchild=S;break;else if(S-datadata&p-lchild!=NULL)p=p-lchild;else if(S-datap-data&p-rchild=NULL)p-rchild=S;brea
2、k;else if(S-datap-data&p-rchild!=NULL)p=p-rchild;return T;Bit *SetBitree() /创建一个二叉排序树Bit *T,*S;int a;T=NULL;printf(输入数据创建一个二叉排序树,以0结束!n);scanf(%d,&a);while(a!=0)S=(Bit *)malloc(sizeof(Bit);S-data=a;S-lchild=S-rchild=NULL;if(T=NULL)T=S;elseT=InBitree(S,T);scanf(%d,&a);return T;Bit *SearchBitree(Bit *
3、T,int a,int b) /查找两结点的最近公共祖先结点Bit *p,*q;p=q=T;while(p!=NULL)if(adata&bdata)q=p;p=p-lchild;else if(ap-data&bp-data)q=p;p=p-rchild;else if(adata&bp-data)|(ap-data&bdata) return p;else if(a=p-data|b=p-data) return q;void main()Bit *T,*Q;int x1,x2;T=SetBitree();if(T=NULL)printf(二叉排序树创建失败，请从新创建!n);else printf(请输入两个结点:n);scanf(%d%d,&x1,&x2);Q=SearchBitree(T,x1,x2);printf(结点%d与结点%d的最近公共祖先结点是%d!n,x1,x2,Q-data);
