• 日期: 2026-11-12
  • 标签: 常规

用二叉树表示家谱关系，并实现各种查找功能（扩展）

目的： 掌握二叉树遍历算法的应用，熟练使用先序、中序、后序三种递归遍历算法进行二叉树问题的求解。

内容： 用C语言编写程序，采用一棵二叉树，表示一个家谱关系（由若干家谱记录构成，每个家谱记录由父亲妻子和儿子的姓名构成，其中姓名是关键字），要求程序具有以下功能。

① 文件操作功能：家谱记录的输入，家谱记录的输出，清除全部文件记录和将家谱记录存盘。要求在输入家谱记录时按从祖先到子孙的顺序输入，第一个家谱记录的父亲域为所有人的祖先。

② 家谱操作功能：用括号表示法输出家谱二叉树，查找某人的所有儿子，查找某人的所有祖先（这里的祖先是指所设计的二叉树结构中某结点的所有祖先结点）。

分析：

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

具体实现：

  1. 家谱记录结构体定义
typedef struct {
    char father[20];
    char wife[20];
    char son[20];
} GenealogyRecord;
  1. 二叉树节点结构体定义
typedef struct TreeNode {
    GenealogyRecord record;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;
  1. 二叉树的创建
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;
}
  1. 二叉树的遍历
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);
}
  1. 查找某人的所有儿子
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);
}
  1. 查找某人的所有祖先
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);
    }
}
  1. 用括号表示法输出家谱二叉树
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(")");
    }
}

完整代码如下：

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

// 家谱记录结构体定义
typedef struct {
    char father[20];
    char wife[20];
    char son[20];
} GenealogyRecord;

// 二叉树节点结构体定义
typedef struct TreeNode {
    GenealogyRecord record;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 创建二叉树
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;
}

// 先序遍历
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);
}

// 查找某人的所有儿子
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);
}

// 查找某人的所有祖先
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);
    }
}

// 用括号表示法输出家谱二叉树
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(")");
    }
}

int main() {
    // 家谱记录
    GenealogyRecord records[] = {
        {"A", "B", "C"},
        {"C", "D", "E"},
        {"C", "D", "F"},
        {"E", "G", "H"},
        {"F", "I", "J"},
        {"H", "K", "L"}
    };
    int n = sizeof(records) / sizeof(records[0]);

    // 创建二叉树
    TreeNode* root = createTree(records, n);

    // 测试输出
    printf("先序遍历：");
    preOrder(root);
    printf("\n");
    printf("中序遍历：");
    inOrder(root);
    printf("\n");
    printf("后序遍历：");
    postOrder(root);
    printf("\n");
    printf("用括号表示法输出家谱二叉树：");
    printTree(root);
    printf("\n");
    printf("查找C的所有儿子：");
    findSons(root, "C");
    printf("\n");
    printf("查找L的所有祖先：");
    findAncestors(root, "L");
    printf("\n");

    return 0;
}
用二叉树表示家谱关系，并实现各种查找功能

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

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