二叉链表实现医院病房病床管理系统

Question

如何添加头结点，已有代码求修改
目前问题：层次遍历时只能输出最近一次插入的结点，
若删除第一个插入的结点会输出错误内容

Answer 1

引自免费微信小程序：皆我百晓生

在C语言中，要实现一个医院病房病床管理系统的二叉链表，首先我们需要定义二叉链表节点结构体，并编写相应的操作函数，如插入、删除和层次遍历等。这里是一个简单的实现示例：

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

// 定义二叉链表节点结构体
typedef struct Node {
    int bed_number; // 病床号
    struct Node* left; // 左子节点
    struct Node* right; // 右子节点
} Node;

// 创建新节点
Node* create_node(int bed_number) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    if (new_node == NULL) {
        printf("Memory allocation failed.\n");
        exit(1);
    }
    new_node->bed_number = bed_number;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}

// 插入节点到二叉树
void insert(Node** root, int bed_number) {
    if (*root == NULL) {
        *root = create_node(bed_number); // 如果根为空，创建新的头结点
    } else {
        Node* current = *root;
        while (current != NULL) {
            if (bed_number < current->bed_number) {
                if (current->left == NULL) {
                    current->left = create_node(bed_number);
                    break;
                }
                current = current->left;
            } else {
                if (current->right == NULL) {
                    current->right = create_node(bed_number);
                    break;
                }
                current = current->right;
            }
        }
    }
}

// 层次遍历打印病床号
void level_order_traversal(Node* root) {
    if (root == NULL) {
        return;
    }

    Queue* queue = create_queue(); // 假设有一个队列数据结构已经实现
    enqueue(queue, root);

    while (!is_empty(queue)) {
        Node* current = dequeue(queue);
        printf("%d ", current->bed_number);

        if (current->left != NULL) {
            enqueue(queue, current->left);
        }
        if (current->right != NULL) {
            enqueue(queue, current->right);
        }
    }
    free_queue(queue); // 释放队列
}

// 删除给定病床号的节点
Node* delete_node(Node** root, int bed_number) {
    if (*root == NULL) {
        return NULL;
    }

    if ((*root)->bed_number == bed_number) { // 如果要删除的是根节点
        Node* temp = *root;
        *root = (*root)->left ? (*root)->left : (*root)->right; // 更新根节点指向左子节点或右子节点
        free(temp);
        return *root;
    } else {
        Node* current = *root;
        while (current != NULL && current->bed_number != bed_number) {
            if (bed_number < current->bed_number) {
                current = current->left;
            } else {
                current = current->right;
            }
        }

        if (current == NULL) { // 节点不存在
            return *root;
        }

        if (current->left == NULL) { // 只有右子节点
            Node* temp = current;
            current = current->right;
            free(temp);
        } else if (current->right == NULL) { // 只有左子节点
            Node* temp = current;
            current = current->left;
            free(temp);
        } else { // 有两个子节点
            Node* min_right = find_min(current->right); // 找到右子树中的最小值
            current->bed_number = min_right->bed_number; // 替换当前节点的值
            current->right = delete_node(&current->right, min_right->bed_number); // 删除找到的最小值节点
        }
        return *root;
    }
}

// 查找右子树中的最小值节点
Node* find_min(Node* node) {
    while (node->left != NULL) {
        node = node->left;
    }
    return node;
}

int main() {
    Node* root = NULL;
    insert(&root, 5);
    insert(&root, 3);
    insert(&root, 7);
    insert(&root, 2);
    insert(&root, 8);

    printf("Level order traversal: ");
    level_order_traversal(root);
    printf("\n");

    delete_node(&root, 3); // 删除病床号为3的节点
    printf("After deleting bed number 3:\n");
    printf("Level order traversal: ");
    level_order_traversal(root);
    printf("\n");

    return 0;
}

这段代码实现了二叉链表的插入、层次遍历和删除功能。注意，在delete_node函数中，我们处理了根节点、只有一个子节点以及有两个子节点的情况，这样可以正确地删除任意位置的节点并保持树的平衡。

这个例子假设已经有了队列的数据结构实现（Queue, enqueue, dequeue, 和 is_empty 函数）。如果你没有这些函数，你需要自己实现它们。同样，对于内存管理和错误检查，也请根据实际情况进行调整。