#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");
}
else
break;
}
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;
}
}
else
p = 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);//路径1
path(bt,q,&S2);//路径2
if(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];
else
return 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;
}
}
}
