#include
#include
#include
#define MAX 100
typedef struct node
{char name[10] ;
struct node lchild, *rchild;
}BTree;
BTree *q[MAX]; /存储队列元素的数组*/
BTree CreatBtree(); / 创建二叉家族树 /
void ScanLevel(BTree *bt); / 按层次顺序遍历二叉家族树 /
int FindAncestry(BTree *bt,char *ch,int flag);
void Precreat(BTree *bt);
void InorderTraverse(BTree *bt);
int main()
{
BTree *head;
int ch;
char cname[10];
while(1)
{
printf("请选择以下操作：\n");
printf ("一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一\n");
printf("1……创建一个二叉家族树\n");
printf("2……按层次输出二叉家族树\n");
printf("3……输出某个成员的所有祖先成员\n");
printf("4……结束程序\n");
printf ("一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一\n");
printf("请选择(1--4)：");
scanf("%d",&ch);
getchar();
switch(ch)
{
case 1: / 创建二叉家族树 /
Precreat(head);
printf("\n二叉家族树创建成功！\n");
printf("\n请按任意键返回主菜单...");
getchar();
break;
case 2:printf("按层次输出二叉家族树：\n");/ 按层次输出家族树 */
ScanLevel(head);
printf("\n中序遍历输出二叉树\n");
InorderTraverse(head);//中序遍历整个数组
printf("\n请按任意键返回主菜单...");
break;
case 3:printf("\n请输入要查找哪个成员的祖先：\n");
scanf("%s",cname);
getchar();
FindAncestry(head,cname,0);
printf("\n请按任意键返回主菜单...");
break;
case 4: exit(0);
}
getchar();
}
}
void ScanLevel(BTree bt) /按层次顺序遍历二叉家族树 /
{ int front=0,rear=0; / 初始化队列的头、尾指针 /
if(bt!=NULL)
{ rear++;
q[rear]=bt; / 将bt所指向的结点入队 /
}
while(front!=rear) / 队列非空 /
{ front++;
bt=q[front]; / 队头结点出队 /
printf (" %s",bt->name); / 输出该结点的数据 /
if(bt->lchild!=NULL)
{
rear++;
q[rear]=bt->lchild; / 将左孩子结点入队 /
}
if(bt->rchild!=NULL)
{rear++;
q[rear]=bt->rchild; / 将右孩子结点入队 */
}
}
}
int FindAncestry(BTree *bt,char *ch,int flag)
{
int flag1=0,flag2=0;
int cond;
if(flag==0&&strcmp(bt->name,ch)==0)
{
printf("这个人是最大的祖先!!!\n");
return 0;
}
flag=1;
if(bt==NULL||(bt->lchild==NULL&&bt->rchild==NULL))
return 0;
cond=(bt->lchild!=NULL)&&(strcmp(bt->lchild->name,ch)==0);
cond=cond||((bt->rchild!=NULL)&&(strcmp(bt->rchild->name,ch)==0));
if(cond)
{
printf("%s，",bt->name);
return 1;
}
else
{
flag1=FindAncestry(bt->lchild,ch,flag);
flag2=FindAncestry(bt->rchild,ch,flag);
if(flag1||flag2)
{
printf("%s，",bt->name);
return 1;
}
else
return 0;
}
}
void Precreat(BTree bt)
{
char ch1[10];
scanf("%s",ch1);
if(strcmp(ch1,"$"))
{
bt=NULL;
}
else
{
bt=(BTree)malloc(sizeof(BTree));
strcpy(bt->name,ch1);
Precreat(bt->lchild);
Precreat(bt->rchild);
}
printf("建立完成");
return;
}
void InorderTraverse(BTree *bt) //中序遍历整个数组
{
if(bt)
{
InorderTraverse(bt->lchild);
printf(" %s",bt->name);
InorderTraverse(bt->rchild);
}
}
写precreat函数，要求$为结束符@为空
