data_structure_exam：17.二叉排序树及其应用

二叉排序树及其应用

查找是日常生活中人们几乎每天都有进行的操作，在各种系统软件中或应用软件中，查找表是最常见的结构之一，在查找过程中同时插入查找表中不存在的元素，或者从查找表中删除已存在的某个数据元素，此类表成为动态查找表，利用二叉排序树完成动态查找表的建立、指定关键字的查找、插入与删除指定关键字结点。

基本要求

从键盘输入一组学生记录建立二叉排序树；
二叉排序树存盘；
由文件恢复内存的二叉排序树；
中序遍历二叉排序树；
求二叉排序树深度；
求二叉排序树的所有节点数和叶子节点数；
向二叉排序树插入一条记录；
从二叉排序树中删除一条记录；
从二叉排序树中查询一条记录；

#include <stdio.h>
#include <stdlib.h>
// 定义二叉排序树的结点结构
typedef struct BSTNode {
    int data; // 关键字数据
    struct BSTNode* left; // 左子树指针
    struct BSTNode* right; // 右子树指针
} BSTNode;
// 创建新结点
BSTNode* createNode(int data) {
    BSTNode* newNode = (BSTNode*)malloc(sizeof(BSTNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
// 向二叉排序树插入结点
BSTNode* insertNode(BSTNode* root, int data) {
    if (root == NULL) {
        // 如果树为空，创建新结点作为根结点
        root = createNode(data);
    }
    else if (data < root->data) {
        // 如果插入数据小于当前结点数据，递归插入左子树
        root->left = insertNode(root->left, data);
    }
    else if (data > root->data) {
        // 如果插入数据大于当前结点数据，递归插入右子树
        root->right = insertNode(root->right, data);
    }
    return root;
}
// 从二叉排序树中删除结点
BSTNode* deleteNode(BSTNode* root, int data) {
    if (root == NULL) {
        return root;
    }
    else if (data < root->data) {
        // 如果删除数据小于当前结点数据，递归删除左子树
        root->left = deleteNode(root->left, data);
    }
    else if (data > root->data) {
        // 如果删除数据大于当前结点数据，递归删除右子树
        root->right = deleteNode(root->right, data);
    }
    else {
        // 找到要删除的结点
        if (root->left == NULL && root->right == NULL) {
            // 如果要删除的结点是叶子结点，直接删除
            free(root);
            root = NULL;
        }
        else if (root->left == NULL) {
            // 如果要删除的结点只有右子树，用右子树结点替代要删除的结点
            BSTNode* temp = root;
            root = root->right;
            free(temp);
        }
        else if (root->right == NULL) {
            // 如果要删除的结点只有左子树，用左子树结点替代要删除的结点
            BSTNode* temp = root;
            root = root->left;
            free(temp);
        }
        else {
            // 如果要删除的结点有左右子树，找到右子树中最小的结点替代要删除的结点
            BSTNode* temp = (root->right);
            root->data = temp->data;
            root->right = deleteNode(root->right, temp->data);
        }
    }
    return root;
}
// 从二叉排序树中查找结点
BSTNode* searchNode(BSTNode* root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    }
    else if (data < root->data) {
        // 如果查找数据小于当前结点数据，递归查找左子树
        return searchNode(root->left, data);
    }
    else {
        // 如果查找数据大于当前结点数据，递归查找右子树
        return searchNode(root->right, data);
    }
}
// 中序遍历二叉排序树
void inorderTraversal(BSTNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}
// 求二叉排序树的深度
int getTreeDepth(BSTNode* root) {
    if (root == NULL) {
        return 0;
    }
    else {
        int leftDepth = getTreeDepth(root->left);
        int rightDepth = getTreeDepth(root->right);
        return (leftDepth > rightDepth) ? (leftDepth + 1) : (rightDepth + 1);
    }
}
// 求二叉排序树的节点数和叶子节点数
void getNodeCount(BSTNode* root, int* nodeCount, int* leafCount) {
    if (root != NULL) {
        (*nodeCount)++;
        if (root->left == NULL && root->right == NULL) {
            (*leafCount)++;
        }
        getNodeCount(root->left, nodeCount, leafCount);
        getNodeCount(root->right, nodeCount, leafCount);
    }
}
// 存储二叉排序树到文件
void saveTreeToFile(BSTNode* root, FILE* file) {
    if (root != NULL) {
        fprintf(file, "%d ", root->data);
        saveTreeToFile(root->left, file);
        saveTreeToFile(root->right, file);
    }
}
// 从文件恢复二叉排序树到内存
BSTNode* restoreTreeFromFile(FILE* file) {
    int data;
    BSTNode* root = NULL;
    while (fscanf(file, "%d", &data) != EOF) {
        root = insertNode(root, data);
    }
    return root;
}
int main() {
    BSTNode* root = NULL;
    int choice, data;
    FILE* file;
    while (1) {
        printf("1. 插入结点\n");
        printf("2. 删除结点\n");
        printf("3. 查找结点\n");
        printf("4. 中序遍历\n");
        printf("5. 求树的深度\n");
        printf("6. 求节点数和叶子节点数\n");
        printf("7. 存盘\n");
        printf("8. 从文件恢复\n");
        printf("9. 退出\n");
        printf("请输入操作编号：");
        scanf("%d", &choice);
        switch (choice) {
        case 1:
            printf("请输入要插入的数据：");
            scanf("%d", &data);
            root = insertNode(root, data);
            break;
        case 2:
            printf("请输入要删除的数据：");
            scanf("%d", &data);
            root = deleteNode(root, data);
            break;
        case 3:
            printf("请输入要查找的数据：");
            scanf("%d", &data);
            if (searchNode(root, data) != NULL) {
                printf("找到了该结点\n");
            }
            else {
                printf("未找到该结点\n");
            }
            break;
        case 4:
            printf("中序遍历结果：");
            inorderTraversal(root);
            printf("\n");
            break;
        case 5:
            printf("树的深度为：%d\n", getTreeDepth(root));
            break;
        case 6:
        {
            int nodeCount = 0, leafCount = 0;
            getNodeCount(root, &nodeCount, &leafCount);
            printf("节点数：%d\n", nodeCount);
            printf("叶子节点数：%d\n", leafCount);
        }
        break;
        case 7:
            file = fopen("bst.txt", "w");
            if (file == NULL) {
                printf("无法打开文件\n");
            }
            else {
                saveTreeToFile(root, file);
                fclose(file);
                printf("已将树存盘到文件\n");
            }
            break;
        case 8:
            file = fopen("bst.txt", "r");
            if (file == NULL) {
                printf("无法打开文件\n");
            }
            else {
                root = restoreTreeFromFile(file);
                fclose(file);
                printf("已从文件恢复树到内存\n");
            }
            break;
        case 9:
            exit(0);
        default:
            printf("无效的操作编号\n");
            break;
        }
    }
    return 0;
}

1. 插入结点
2. 删除结点
3. 查找结点
4. 中序遍历
5. 求树的深度
6. 求节点数和叶子节点数
7. 存盘
8. 从文件恢复
9. 退出
请输入操作编号：