使用循环队列实现二叉搜索树中序遍历的代码错误排查与修正

常见错误点排查 #

结合你描述的乱码、重复打印问题，大概率是以下几个原因导致：

• 循环队列容量不足：循环队列需要预留1个空位区分空/满状态，若容量小于节点数+1，会触发数据覆盖或入队失败，引发乱码。
• 递归遍历逻辑漏洞：未在递归开头判断节点是否为空，导致访问空指针读取无效内存；或入队操作位置错误，导致节点重复入队。
• 队列操作逻辑错误：头尾指针更新未取模、空/满判断条件错误，导致出队时重复读取或访问无效地址。

修正后的完整代码 #

以下是能正确实现需求的代码，包含树结构构建、循环队列操作、中序遍历及输出：

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

// 二叉树节点结构
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 循环队列结构
typedef struct Queue {
    TreeNode **data;
    int front;
    int rear;
    int capacity;
} Queue;

// 初始化循环队列
Queue* initQueue(int capacity) {
    Queue *q = (Queue*)malloc(sizeof(Queue));
    q->data = (TreeNode**)malloc(sizeof(TreeNode*) * capacity);
    q->front = 0;
    q->rear = 0;
    q->capacity = capacity;
    return q;
}

// 判断队列是否为空
int isEmpty(Queue *q) {
    return q->front == q->rear;
}

// 判断队列是否已满
int isFull(Queue *q) {
    return (q->rear + 1) % q->capacity == q->front;
}

// 入队操作
void enqueue(Queue *q, TreeNode *node) {
    if (isFull(q)) {
        printf("Queue overflow!\n");
        return;
    }
    q->data[q->rear] = node;
    q->rear = (q->rear + 1) % q->capacity;
}

// 出队操作
TreeNode* dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue underflow!\n");
        return NULL;
    }
    TreeNode *node = q->data[q->front];
    q->front = (q->front + 1) % q->capacity;
    return node;
}

// 销毁队列
void destroyQueue(Queue *q) {
    free(q->data);
    free(q);
}

// 创建新二叉树节点
TreeNode* createNode(int data) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 构建题目指定的BST
TreeNode* buildBST() {
    TreeNode *root = createNode(6);
    root->left = createNode(2);
    root->right = createNode(7);
    root->left->left = createNode(1);
    root->left->right = createNode(4);
    root->left->right->left = createNode(3);
    root->left->right->right = createNode(5);
    return root;
}

// 中序遍历：将节点依次入队
void inorderEnqueue(TreeNode *root, Queue *q) {
    if (root == NULL) return;
    inorderEnqueue(root->left, q);
    enqueue(q, root);
    inorderEnqueue(root->right, q);
}

int main() {
    TreeNode *root = buildBST();
    // 树共7个节点，循环队列容量设为8（预留1个空位）
    Queue *q = initQueue(8);
    
    inorderEnqueue(root, q);
    
    printf("Inorder Traversal :  ");
    while (!isEmpty(q)) {
        TreeNode *node = dequeue(q);
        printf("%d ", node->data);
    }
    printf("\n");
    
    destroyQueue(q);
    // 可补充树的销毁函数避免内存泄漏
    return 0;
}

代码修正说明 #

1. 队列容量设置：针对7个节点的树，队列容量设为8，满足循环队列空/满判断的预留空位要求。
2. 递归判空：inorderEnqueue开头先判断节点是否为空，避免访问无效内存。
3. 队列操作规范化：头尾指针更新时取模，确保循环队列的正确循环逻辑；严格实现空/满判断条件。

前序、后序遍历扩展 #

只需修改遍历入队的函数逻辑即可：

// 前序遍历入队
void preorderEnqueue(TreeNode *root, Queue *q) {
    if (root == NULL) return;
    enqueue(q, root);
    preorderEnqueue(root->left, q);
    preorderEnqueue(root->right, q);
}

// 后序遍历入队
void postorderEnqueue(TreeNode *root, Queue *q) {
    if (root == NULL) return;
    postorderEnqueue(root->left, q);
    postorderEnqueue(root->right, q);
    enqueue(q, root);
}

内容的提问来源于stack exchange，提问作者bFur4list