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

源代码：

#include \#include \typedef struct node {

int 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->data>p->data&&p->rchild==NULL){ p->rchild=S; break; }

else if(S->data>p->data&&p->rchild!=NULL) p=p->rchild; }

return T; }

Bit *SetBitree(){ //创建一个二叉排序树 Bit *T,*S; int a; T=NULL;

printf(\输入数据创建一个二叉排序树,以0结束!\\n\ scanf(\ while(a!=0){

S=(Bit *)malloc(sizeof(Bit)); S->data=a;

S->lchild=S->rchild=NULL; if(T==NULL) T=S; else

T=InBitree(S,T); scanf(\ }

return T;

}

Bit *SearchBitree(Bit *T,int a,int b){ //查找两结点的最近公共祖先结点 Bit *p,*q; p=q=T;

while(p!=NULL){

if(adata&&bdata){ q=p;

p=p->lchild; }

else if(a>p->data&&b>p->data){ q=p;

p=p->rchild; }

else if((adata&&b>p->data)||(a>p->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(\ Q=SearchBitree(T,x1,x2);

printf(\结点%d与结点%d的最近公共祖先结点是%d!\\n\} }