• 日期: 2027-05-23
  • 标签: 常规

使用 C 语言编写一个完成的可运行的程序，采用一棵二叉树，表示一个家谱关系（由若干家谱记录构成，每个家谱记录由父亲妻子和儿子的姓名构成，其中姓名是关键字），要求程序具有以下功能。 ①文件操作功能：家谱记录的输入，家谱记录的输出，清除全部文件记录和将家谱记录存盘。要求在输入家谱记录时按从祖先到子孙的顺序输入，第一个家谱记录的父亲域为所有人的祖先。 ②家谱操作功能：用括号表示法输出家谱二叉树，查找某人的所有儿子，查找某人的所有祖先（这里的祖先是指所设计的二叉树结构中某结点的所有祖先结点）。

以下是该程序的代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node {
    char name[20];
    struct node *father;
    struct node *mother;
    struct node *left;
    struct node *right;
} Node;

Node *root = NULL;

void insert(Node *node, char *fatherName, char *motherName, char *name);
void printPreorder(Node *node);
void printParentheses(Node *node);
void printChildren(Node *node, char *name);
void printAncestors(Node *node, char *name);
void clear(Node *node);
void saveToFile(Node *node, FILE *fp);
void loadFromFile(FILE *fp);

int main() {
    char command[10];
    while (1) {
        printf("请输入命令：");
        scanf("%s", command);
        if (strcmp(command, "input") == 0) {
            char fatherName[20], motherName[20], name[20];
            printf("请输入父亲、母亲和儿子的姓名（以空格分隔）：");
            scanf("%s %s %s", fatherName, motherName, name);
            insert(root, fatherName, motherName, name);
        } else if (strcmp(command, "output") == 0) {
            printParentheses(root);
            printf("\n");
        } else if (strcmp(command, "children") == 0) {
            char name[20];
            printf("请输入要查找儿子的人的姓名：");
            scanf("%s", name);
            printChildren(root, name);
        } else if (strcmp(command, "ancestors") == 0) {
            char name[20];
            printf("请输入要查找祖先的人的姓名：");
            scanf("%s", name);
            printAncestors(root, name);
            printf("\n");
        } else if (strcmp(command, "clear") == 0) {
            clear(root);
            root = NULL;
        } else if (strcmp(command, "save") == 0) {
            FILE *fp = fopen("data.txt", "w");
            saveToFile(root, fp);
            fclose(fp);
            printf("保存成功！\n");
        } else if (strcmp(command, "load") == 0) {
            FILE *fp = fopen("data.txt", "r");
            loadFromFile(fp);
            fclose(fp);
            printf("载入成功！\n");
        } else if (strcmp(command, "exit") == 0) {
            break;
        } else {
            printf("无效命令，请重新输入！\n");
        }
    }
    return 0;
}

void insert(Node *node, char *fatherName, char *motherName, char *name) {
    if (node == NULL) {
        node = (Node *) malloc(sizeof(Node));
        strcpy(node->name, name);
        node->father = (Node *) malloc(sizeof(Node));
        strcpy(node->father->name, fatherName);
        node->mother = (Node *) malloc(sizeof(Node));
        strcpy(node->mother->name, motherName);
        node->left = NULL;
        node->right = NULL;
        if (root == NULL) {
            root = node;
        }
    } else if (strcmp(node->name, fatherName) == 0) {
        Node *child = (Node *) malloc(sizeof(Node));
        strcpy(child->name, name);
        child->father = node;
        child->mother = (Node *) malloc(sizeof(Node));
        strcpy(child->mother->name, motherName);
        child->left = NULL;
        child->right = NULL;
        if (node->left == NULL) {
            node->left = child;
        } else {
            Node *temp = node->left;
            while (temp->right != NULL) {
                temp = temp->right;
            }
            temp->right = child;
        }
    } else {
        insert(node->left, fatherName, motherName, name);
        insert(node->right, fatherName, motherName, name);
    }
}

void printPreorder(Node *node) {
    if (node != NULL) {
        printf("%s ", node->name);
        printPreorder(node->left);
        printPreorder(node->right);
    }
}

void printParentheses(Node *node) {
    if (node != NULL) {
        printf("%s", node->name);
        if (node->left != NULL || node->right != NULL) {
            printf("(");
            printParentheses(node->left);
            if (node->right != NULL) {
                printf(",");
                printParentheses(node->right);
            }
            printf(")");
        }
    }
}

void printChildren(Node *node, char *name) {
    if (node != NULL) {
        if (strcmp(node->name, name) == 0) {
            Node *child = node->left;
            while (child != NULL) {
                printf("%s ", child->name);
                child = child->right;
            }
            printf("\n");
        } else {
            printChildren(node->left, name);
            printChildren(node->right, name);
        }
    }
}

void printAncestors(Node *node, char *name) {
    if (node != NULL) {
        if (strcmp(node->name, name) == 0) {
            return;
        }
        printAncestors(node->father, name);
        printf("%s ", node->name);
        printAncestors(node->mother, name);
    }
}

void clear(Node *node) {
    if (node != NULL) {
        clear(node->left);
        clear(node->right);
        free(node->father);
        free(node->mother);
        free(node);
    }
}

void saveToFile(Node *node, FILE *fp) {
    if (node != NULL) {
        fprintf(fp, "%s %s %s\n", node->father->name, node->mother->name, node->name);
        saveToFile(node->left, fp);
        saveToFile(node->right, fp);
    }
}

void loadFromFile(FILE *fp) {
    char fatherName[20], motherName[20], name[20];
    while (fscanf(fp, "%s %s %s\n", fatherName, motherName, name) != EOF) {
        insert(root, fatherName, motherName, name);
    }
}

在该程序中，我们定义了一个结构体Node，用于表示家谱树的每个节点。每个节点包含一个姓名、一个父亲节点、一个母亲节点、一个左子节点和一个右子节点。我们还定义了一个全局变量root，用于保存家谱树的根节点。

在main函数中，我们通过循环读取用户输入的命令，并根据命令执行相应的操作。如果是输入命令（input），则读取父亲、母亲和儿子的姓名，并调用insert函数将新节点插入家谱树中。如果是输出命令（output），则调用printParentheses函数以括号表示法输出家谱树。如果是查找儿子命令（children），则读取要查找的人的姓名，并调用printChildren函数查找其所有儿子。如果是查找祖先命令（ancestors），则读取要查找的人的姓名，并调用printAncestors函数查找其所有祖先。如果是清除命令（clear），则调用clear函数清除整个家谱树。如果是保存命令（save），则将家谱树保存到文件中。如果是载入命令（load），则从文件中读取家谱树。

在insert函数中，我们首先判断当前节点是否为空，如果为空则创建一个新节点，并将其设置为根节点（如果根节点为空）。如果当前节点不为空，并且其姓名与父亲的姓名匹配，则创建一个新节点，并将其插入到当前节点的子节点列表中。否则，递归调用insert函数，继续在当前节点的左子树和右子树中查找与父亲姓名匹配的节点。

在printPreorder函数中，我们采用先序遍历的方式输出家谱树中每个节点的姓名。在printParentheses函数中，我们采用括号表示法输出家谱树。

在printChildren函数中，我们首先判断当前节点的姓名是否与要查找的姓名匹配，如果匹配则遍历当前节点的子节点列表，并输出所有子节点的姓名。否则，递归调用printChildren函数，继续在当前节点的左子树和右子树中查找要查找的姓名。

在printAncestors函数中，我们首先判断当前节点的姓名是否与要查找的姓名匹配，如果匹配则直接返回。否则，递归调用printAncestors函数，先输出当前节点的父亲节点的姓名，然后递归调用printAncestors函数，输出当前节点的母亲节点的姓名。

在clear函数中，我们首先递归调用clear函数，清除当前节点的左子树和右子树，然后释放当前节点的父亲节点、母亲节点和自身的内存。

在saveToFile函数中，我们采用前序遍历的方式将家谱树输出到文件中。

在loadFromFile函数中，我们从文件中读取父亲、母亲和儿子的姓名，并调用insert函数将新节点插入家谱树中。

C语言实现家谱树：二叉树存储，查找功能扩展

原文地址: https://www.cveoy.top/t/topic/opT0 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录