C语言N叉树的层序遍历

Question

按上图要求，编写一个C语言程序，完成N叉树的层序遍历。C语言数据结构与算法

Answer 1

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

为了实现N叉树的层序遍历，你需要定义一个结构体来表示节点，并创建一个辅助函数来执行广度优先搜索（BFS）。下面是一个完整的C语言程序，用于实现这个功能：

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

// 定义N叉树的节点结构体
typedef struct Node {
    int value;
    struct Node** children; // 孩子链表，用指向Node*的指针数组表示
    int num_children; // 孩子数量
} Node;

// 创建新节点
Node* create_node(int value, int num_children) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->value = value;
    newNode->children = (Node**)malloc(num_children * sizeof(Node*));
    newNode->num_children = num_children;
    return newNode;
}

// 释放节点及其所有子节点
void free_node(Node* node) {
    for (int i = 0; i < node->num_children; ++i) {
        if (node->children[i]) {
            free_node(node->children[i]);
        }
    }
    free(node->children);
    free(node);
}

// 层序遍历辅助函数，使用队列进行广度优先搜索
void level_order_traversal(Node* root, void (*print)(int)) {
    if (!root) {
        return;
    }

    // 初始化队列
    Queue* queue = create_queue();
    enqueue(queue, root);

    while (!is_empty(queue)) {
        Node* current = dequeue(queue);
        print(current->value);

        for (int i = 0; i < current->num_children; ++i) {
            if (current->children[i]) {
                enqueue(queue, current->children[i]);
            }
        }
    }

    destroy_queue(queue);
}

// 打印节点值
void print_value(int value) {
    printf("%d ", value);
}

int main() {
    // 根据输入构建N叉树
    int n;
    scanf("%d", &n);
    char input[n][10];
    Node* root = NULL;
    for (int i = 0; i < n; ++i) {
        scanf("%s", input[i]);
        if (input[i][0] == 'R') { // 如果是根节点
            int root_index = atoi(input[i] + 2);
            if (root == NULL) {
                root = create_node(root_index, root_index - 1);
            } else {
                Node* current = root;
                for (int j = 0; j < root_index - 1; ++j) {
                    current = current->children[j];
                }
                current->children[root_index - 1] = create_node(i, 0); // 叶子节点
            }
        } else {
            int parent_index = atoi(input[i] + 1);
            int child_index = atoi(input[i] + 3);
            if (parent_index > 0 && child_index >= 0) {
                Node* parent = find_parent(root, parent_index - 1);
                parent->children[child_index - 1] = create_node(i, 0); // 叶子节点
            }
        }
    }

    // 层序遍历并打印结果
    level_order_traversal(root, print_value);
    printf("\n");

    // 释放内存
    free_node(root);

    return 0;
}

// 队列相关操作
typedef struct Queue {
    int size;
    int front, rear;
    void* elements[];
} Queue;

Queue* create_queue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->size = 10;
    queue->front = queue->rear = -1;
    return queue;
}

void enqueue(Queue* queue, void* element) {
    if ((queue->rear + 1) % queue->size == queue->front) {
        printf("Queue is full\n");
        exit(1);
    }
    queue->rear = (queue->rear + 1) % queue->size;
    queue->elements[queue->rear] = element;
}

void* dequeue(Queue* queue) {
    if (queue->front == queue->rear) {
        printf("Queue is empty\n");
        exit(1);
    }
    void* element = queue->elements[queue->front];
    queue->front = (queue->front + 1) % queue->size;
    return element;
}

bool is_empty(Queue* queue) {
    return queue->front == queue->rear;
}

void destroy_queue(Queue* queue) {
    free(queue);
}

// 查找父节点
Node* find_parent(Node* root, int index) {
    Node* current = root;
    for (int i = 0; i <= index; ++i) {
        current = current->children[i];
    }
    return current;
}

这段代码首先定义了一个Node结构体来表示N叉树的节点，然后提供了创建、删除节点以及处理队列的相关函数。在main函数中，我们根据输入构建了N叉树，并通过调用level_order_traversal函数实现了层序遍历。

注意：这里的代码没有包含错误检查和边界条件处理，实际应用中应增加这些部分以确保程序的健壮性。同时，队列实现简化了，仅适用于本示例中的大小，对于更复杂的情况可能需要动态调整队列大小。