思路:将两个不同节点的所有祖先分别存放在两个对应栈中,最后一次两个栈出栈数相同即为最近公共祖先。
创建数据:
typedef struct tree{
struct tree *lchild,*rchild,*parent;
char data;
}CStree,*CTree;
typedef struct{
CStree *Zx[maxlen];
int top;
}Z_list;
CStree *Q[maxlen];
算法:
创建树:CStree *Ctree();
查找节点:CStree *C_Z(char a);
查找祖先并放入栈中: Z_list *find_par(Z_list *z, CStree *T);
查找到最近的公共祖先: void Z_X(CStree *T);
完整代码:
#include<stdio.h>
#include<stdlib.h>
#define maxlen 50
typedef struct tree{
struct tree *lchild,*rchild,*parent;
char data;
}CStree,*CTree;
typedef struct{
CStree *Zx[maxlen];
int top;
}Z_list;
CStree *Q[maxlen];
CStree *Ctree(){
int front=1;
int rear=0;
char ch;
CStree *T,*S;//T:根节点;S:创建
T=NULL;
ch=getchar();
while(ch!='#'){//#终止符
S=NULL;
if(ch!='@'){//@虚指针
S=(CTree)malloc(sizeof(CStree));
S->data=ch;
S->lchild=NULL;
S->rchild=NULL;
}
rear++;Q[rear]=S;
if(rear==1){
T=S;
}else{
if(S!=NULL && Q[front]!=NULL){
if(rear%2==0){
Q[front]->lchild=Q[rear];
}else{
Q[front]->rchild=Q[rear];
}
Q[rear]->parent=Q[front];
}
if(rear%2==1) front++;
}
ch=getchar();
}
getchar();
return T;
}
CStree *C_Z(char a){
int i=1;
for(;i<maxlen;i++){
if(Q[i]->data==a){
return Q[i];
}
}
}
Z_list *find_par(Z_list *z, CStree *T){
while(T->parent!=NULL){
z->top++;
z->Zx[z->top]=T->parent;
T=T->parent;
}
return z;
}
void Z_X(CStree *T){
Z_list *z1=(Z_list*)malloc(sizeof(Z_list));z1->top=-1;
Z_list *z2=(Z_list*)malloc(sizeof(Z_list));z2->top=-1;
CStree *L1=(CTree)malloc(sizeof(CStree));
CStree *L2=(CTree)malloc(sizeof(CStree));
char a1,a2;//输入两个节点
scanf("%c %c",&a1,&a2);
getchar();
L1=C_Z(a1);//查找a1节点
L2=C_Z(a2);//查找a2节点
z1=find_par(z1,L1);//建立节点1的祖先栈
z2=find_par(z2,L2);//建立节点2的祖先栈
while((z1->Zx[z1->top])==(z2->Zx[z2->top])){
if(z1->top==0 || z2->top==0 ){
break;
}
if((z1->Zx[z1->top-1]->data)!=(z2->Zx[z2->top-1]->data))
break;
z1->top--;
z2->top--;
}
printf("公共祖先:%c\n",z1->Zx[z1->top]->data);
}
int main(){
CStree *T;
T=Ctree();
Z_X(T);
return 0;
}