#include
#define TRUE 1 #define FALSE 0
#define Stack_Size 20 typedef struct Node {
char data;struct Node *LChild;struct Node *RChild;
}BiTNode,*BiTree;
typedef struct {
BiTree elem[Stack_Size];int top;
}SeqStack;
SeqStack S1,S2; BiTree p,bt;
int Select_menu(); void CreateTree(BiTree *bt); void PreOrdere(BiTree bt); void path(BiTree bt, char ch, SeqStack *S); BiTree FindParents(BiTree bt,char p,char q,SeqStack S1,SeqStack S2);
int Select_menu() {
int a;printf("求二叉树中p与q结点的最近共同祖先管理程序\n");printf("-------------------------------------------\n");printf("1.利用扩展的先序序列建立二叉树\n");printf("2.输出已建立的二叉树：\n");printf("3.你想求哪两个结点的最近共同祖先，请输入p和q\n");printf("4.找出p与q结点最近的共同祖先\n");printf("0.退出该管理系统\n");printf("===============================\n");printf("请输入0--4:\n");for(;;){scanf("%d",&a);if(a>4||a<0){printf("输入错误，请重新输入：\n");}elsebreak;}return a;
}
void CreateTree(BiTree *bt)//先序建立二叉树 {
char ch;scanf(" %c",&ch);if(ch=='.')*bt=NULL;else{*bt=(BiTree)malloc(sizeof(BiTNode));(*bt)->data=ch;CreateTree(&((*bt)->LChild));CreateTree(&((*bt)->RChild));}
}
void PreOrdere(BiTree bt)//先序输出二叉树 {
if(bt!=NULL){printf("%3c",bt->data);PreOrdere(bt->LChild);PreOrdere(bt->RChild);}
}
void path(BiTree bt, char ch, SeqStack *S) {
BiTNode *p, *q;S->top = -1;q = NULL, p = bt;while (p != NULL|| S->top !=-1){while (p != NULL){S->top++;if (S->top >= Stack_Size){return;}S->elem[S->top] = p;p = p->LChild;}if (S->top > -1){p = S->elem[S->top];if (p->RChild == NULL || p->RChild == q){if (p->data == ch){return;}else{q = p;S->elem[S->top] = NULL;S->top--;p = NULL;}}elsep = p->RChild;}}
}
/* TODO:找出共同祖先 功能描述：找出p和q节点的最近共同祖先 例如：树结构为 A
B C则BC的最近共同先祖为A
参数：BiTree类型指针bt，char型参数p、q, SeqStack型栈S1 、S2 返回值说明：返回其共同祖先 */ BiTree FindParents(BiTree bt,char p,char q,SeqStack S1,SeqStack S2) {
BiTree t,p1,p2;path(bt,p,&S1);//路径1path(bt,q,&S2);//路径2if(S1.top==-1||S2.top==-1)//没有找到路径return NULL;while(S1.elem[S1.top]==S2.elem[S2.top]&&S1.top!=0&&S2.top!=0)//路径公共部分{S1.top--;S2.top--;}if(S1.top==0) //若p是q的祖先，或q是p的祖先return S1.elem[0];elsereturn S2.elem[0];
}
int main(void) {
char p,q;BiTree s;bt=(BiTree)malloc(sizeof(BiTNode));for(;;){switch(Select_menu()){case 1:printf("请输入你要建立的二叉树的元素(‘.’表示空)：\n");CreateTree(&bt);break;case 2:printf("您刚刚建立的二叉树为:\n");PreOrdere(bt);printf("\n");break;case 3:printf("请输入你要查找的两个节点:\n");getchar();scanf("%c%c",&p,&q);getchar();break;case 4:s=FindParents(bt,p,q,S1,S2);printf("你想找的共同祖先为:%c\n",s->data);break;case 0:printf("再见啦！\n");return 0;}}
}
