编写算法在二叉排序树上找出任意两个不同节点的最近公共祖先

《编写算法在二叉排序树上找出任意两个不同节点的最近公共祖先》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、源代码：#include"stdio.h"#include"stdlib.h"typedefstructnode{intdata;structnode*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;}elseif(S->datadata&&p->lchild!=NULL)p=p->lchild;elseif(S

2、->data>p->data&&p->rchild==NULL){p->rchild=S;break;}elseif(S->data>p->data&&p->rchild!=NULL)p=p->rchild;}returnT;}Bit*SetBitree(){//创建一个二叉排序树Bit*T,*S;inta;T=NULL;printf("输入数据创建一个二叉排序树,以0结束!");scanf("%d",&a);while(a!=0){S=(Bit*)malloc(sizeof(Bit));S->data=a;S->lchild=S->

3、rchild=NULL;if(T==NULL)T=S;elseT=InBitree(S,T);scanf("%d",&a);}returnT;}Bit*SearchBitree(Bit*T,inta,intb){//查找两结点的最近公共祖先结点Bit*p,*q;p=q=T;while(p!=NULL){if(adata&&bdata){q=p;p=p->lchild;}elseif(a>p->data&&b>p->data){q=p;p=p->rchild;}elseif((adata&&b>p->data)

4、

5、(

6、a>p->data&&bdata))returnp;elseif(a==p->data

7、

8、b==p->data)returnq;}}voidmain(){Bit*T,*Q;intx1,x2;T=SetBitree();if(T==NULL)printf("二叉排序树创建失败，请从新创建!");else{printf("请输入两个结点:");scanf("%d%d",&x1,&x2);Q=SearchBitree(T,x1,x2);printf("结点%d与结点%d的最近公共祖先结点是%d!",x1,x2,Q->data

9、);}}