C语言构建二叉树求助：按索引规则插入节点（无数组/链表/索引字段）

实现思路 #

你的插入规则对应完全二叉树的层序结构，要在不使用数组/链表存储元素序列、不给节点加索引字段的前提下完成插入，我们可以用一个临时队列追踪当前待填充子节点的节点：

• 第一个输入元素作为根节点，加入队列。
• 后续每个元素依次填充队列头部节点的左子、右子：
  1. 若头部节点左子为空，将新节点设为左子并加入队列。
  2. 若左子已存在，将新节点设为右子并加入队列，同时将头部节点移出队列（因为它的左右子都已填充完毕）。

修改后的完整代码 #

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

typedef struct Node *NodePtr;
typedef struct {
    int val;
    NodePtr left;
    NodePtr right;
} Node;

// 辅助队列结构，用于追踪待填充子节点的节点
typedef struct QueueNode {
    NodePtr treeNode;
    struct QueueNode* next;
} QueueNode;

typedef struct {
    QueueNode* front;
    QueueNode* rear;
} Queue;

// 队列操作函数
void initQueue(Queue* q) {
    q->front = q->rear = NULL;
}

void enqueue(Queue* q, NodePtr node) {
    QueueNode* newQueueNode = (QueueNode*)malloc(sizeof(QueueNode));
    newQueueNode->treeNode = node;
    newQueueNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newQueueNode;
        return;
    }
    q->rear->next = newQueueNode;
    q->rear = newQueueNode;
}

NodePtr dequeue(Queue* q) {
    if (q->front == NULL) return NULL;
    QueueNode* temp = q->front;
    NodePtr treeNode = temp->treeNode;
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    return treeNode;
}

int isQueueEmpty(Queue* q) {
    return q->front == NULL;
}

// 插入元素函数（修改为传入根节点指针的指针，以便修改根节点）
void insert_element(NodePtr* root, Queue* q, int element) {
    NodePtr newNode = (NodePtr)malloc(sizeof(Node));
    newNode->val = element;
    newNode->left = newNode->right = NULL;

    if (*root == NULL) {
        *root = newNode;
        enqueue(q, newNode);
        return;
    }

    NodePtr current = q->front->treeNode;
    if (current->left == NULL) {
        current->left = newNode;
        enqueue(q, newNode);
    } else {
        current->right = newNode;
        enqueue(q, newNode);
        dequeue(q);
    }
}

// 递归销毁树，避免内存泄漏
void destroyTree(NodePtr root) {
    if (root == NULL) return;
    destroyTree(root->left);
    destroyTree(root->right);
    free(root);
}

// 层序遍历输出，用于验证树结构
void levelOrderTraversal(NodePtr root) {
    if (root == NULL) return;
    Queue q;
    initQueue(&q);
    enqueue(&q, root);
    printf("Level order traversal: ");
    while (!isQueueEmpty(&q)) {
        NodePtr node = dequeue(&q);
        printf("%d ", node->val);
        if (node->left != NULL) enqueue(&q, node->left);
        if (node->right != NULL) enqueue(&q, node->right);
    }
    printf("\n");
}

int main(void) {
    int n, i, element;
    printf("Enter number of elements: \n");
    if (scanf("%d", &n) != 1 || n <= 0) {
        printf("Input Error!\n");
        return -1;
    }
    printf("Enter elements: \n");

    NodePtr root = NULL;
    Queue q;
    initQueue(&q);

    for (i = 0; i < n; i++) {
        if (scanf("%d", &element) != 1) {
            printf("Input Error!\n");
            destroyTree(root);
            return -1;
        }
        insert_element(&root, &q, element);
    }

    // 验证树结构
    levelOrderTraversal(root);

    // 释放内存
    destroyTree(root);

    return 0;
}

关键说明 #

1. 队列的作用：仅作为临时辅助工具，追踪需要填充子节点的节点，没有用数组/链表存储输入的元素序列，符合你的限制条件。
2. 根节点的处理：通过二级指针NodePtr* root传入根节点，确保首次插入时能正确创建根节点。
3. 内存管理：添加了destroyTree函数递归释放所有节点内存，避免内存泄漏。
4. 输入校验：完善了输入合法性检查，包括节点数量必须为正整数、输入元素必须是整数。

内容的提问来源于stack exchange，提问作者The Bulletbroof Joker