用二叉树表示家谱关系并实现各种查找功能扩展目的：掌握二叉树遍历算法的应用熟练使用先序、中序、后序三种递归遍历算法进行二叉树问题的求解。内容：用c语言编写程序采用一棵二叉树表示一个家谱关系由若干家谱记录构成每个家谱记录由父亲妻子和儿子的姓名构成其中姓名是关键字要求程序具有以下功能。①文件操作功能：家谱记录的输入家谱记录的输出清除全部文件记录和将家谱记录存盘。要求在输入家谱记录时按从祖先到子孙的顺序输

分析：

要实现这个功能，首先需要定义一个家谱记录的结构体，包含父亲、妻子和儿子的姓名等信息。然后定义一个二叉树节点结构体，包含家谱记录和左右子节点的指针。接着，需要实现二叉树的创建、遍历、查找、输出等操作。

具体实现：

1. 家谱记录结构体定义

typedef struct {
    char father[20];
    char wife[20];
    char son[20];
} GenealogyRecord;

2. 二叉树节点结构体定义

typedef struct TreeNode {
    GenealogyRecord record;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

3. 二叉树的创建

TreeNode* createTree(GenealogyRecord* records, int n) {
    // 创建根节点
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->record = records[0];
    root->left = NULL;
    root->right = NULL;
    // 逐个插入节点
    for (int i = 1; i < n; i++) {
        TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
        node->record = records[i];
        node->left = NULL;
        node->right = NULL;
        TreeNode* p = root;
        while (1) {
            if (strcmp(node->record.father, p->record.son) == 0) {
                if (p->left == NULL) {
                    p->left = node;
                    break;
                } else {
                    p = p->left;
                }
            } else if (strcmp(node->record.father, p->record.wife) == 0) {
                if (p->right == NULL) {
                    p->right = node;
                    break;
                } else {
                    p = p->right;
                }
            } else {
                printf("Invalid record!\n");
                break;
            }
        }
    }
    return root;
}

4. 二叉树的遍历

void preOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%s ", root->record.son);
    preOrder(root->left);
    preOrder(root->right);
}

void inOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left);
    printf("%s ", root->record.son);
    inOrder(root->right);
}

void postOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    printf("%s ", root->record.son);
}

5. 查找某人的所有儿子

void findSons(TreeNode* root, char* name) {
    if (root == NULL) {
        return;
    }
    if (strcmp(root->record.father, name) == 0) {
        printf("%s ", root->record.son);
    }
    findSons(root->left, name);
    findSons(root->right, name);
}

6. 查找某人的所有祖先

void findAncestors(TreeNode* root, char* name) {
    if (root == NULL) {
        return;
    }
    if (strcmp(root->record.son, name) == 0) {
        return;
    }
    if (strcmp(root->record.wife, name) == 0) {
        printf("%s ", root->record.father);
        findAncestors(root->left, root->record.father);
        findAncestors(root->right, root->record.father);
    } else {
        findAncestors(root->left, name);
        findAncestors(root->right, name);
    }
}

7. 用括号表示法输出家谱二叉树

void printTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%s", root->record.son);
    if (root->left != NULL || root->right != NULL) {
        printf("(");
        printTree(root->left);
        if (root->right != NULL) {
            printf(",");
            printTree(root->right);
        }
        printf(")");
    }
}

完整代码如下