实验五

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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 main() {
    BTree* head;
    int ch;
    char cname[10];
    while (1) {
        printf("请选择以下操作：\n");
        printf("1. 创建一个二叉家族树\n");
        printf("2. 按层次输出二叉家族树\n");
        printf("3. 输出某个成员的所有祖先成员\n");
        printf("4. 结束程序\n");
        printf("请选择(1--4)：");
        scanf("%d", &ch);
        getchar();
        switch (ch) {
        case 1: head = CreatBtree(); 
            printf("\n二叉家族树创建成功！\n");
            printf("\n请按任意键返回主菜单...");
            getchar();
            break;
        case 2:    printf("按层次输出二叉家族树：\n");
            ScanLevel(head); 
            printf("\n请按任意键返回主菜单...");
            break;
        case 3:    printf("\n请输入要查找哪个成员的祖先：\n");
            scanf("%s", cname);
            getchar();
            FindAncestry(head, cname);
            printf("\n请按任意键返回主菜单...");
            break;
        case 4: exit(0);
        }
        getchar();
    }
    return 0;
}

BTree* CreatBtree() {
    char ch1[10];
    int front, rear;
    int flag = 0;
    BTree* root, * s;
    front = 1, rear = 0;
    root = NULL;
    printf("请按层次顺序输入家族成员姓名，空缺处输入@，结束符为$\n");
    scanf("%s", ch1);
    while (strcmp(ch1, "$")) {
        s = (BTree*)malloc(sizeof(BTree));
        strcpy(s->name, ch1);
        s->lchild = s->rchild = NULL;
        rear++;
        q[rear] = s;
        if (rear == 1)
            root = s;
        else {
            if (q[front] && s) {
                if (rear % 2 == 0)
                    q[front]->lchild = s;
                else {
                    q[front]->rchild = s;
                    front++;
                    flag = 0;
                }
            }
            else {
                flag++;
                if (flag == 2) {
                    front++;
                    flag = 0;
                }
            }
        }
        scanf("%s", ch1);
    }
    return root;
}

void ScanLevel(BTree* bt) {
    int front = 0, rear = 0;
    if (bt != NULL) {
        rear++;
        q[rear] = bt;
    }
    while (front != rear) {
        front++;
        bt = q[front];
        printf("%s ", bt->name);
        if (bt->lchild != NULL)
            rear++;
        if (bt->rchild != NULL)
            rear++;
    }
}

int FindAncestry(BTree* t, char* ch) {
    int flagl = 0, flag2 = 0;
    int cond;
    if (t == NULL || (t->lchild == NULL && t->rchild == NULL))
        return 0;
    cond = (t->lchild != NULL) && (strcmp(t->lchild->name, ch) == 0);
    cond = cond || ((t->rchild != NULL) && (strcmp(t->rchild->name, ch) == 0));
    if (cond) {
        printf("%s,", t->name);
        return 1;
    }
    else {
        flagl = FindAncestry(t->lchild, ch);
        flag2 = FindAncestry(t->rchild, ch);
        if (flagl || flag2) {
            printf("%s,", t->name);
            return 1;
        }
        else
            return 0;
    }
}

---

• 分类： 未分类
• 标签： 无标签