基于链表实现队列编写树前序遍历的代码报错问题求解

当前代码报错的本质是队列存储节点和二叉树节点混用了同一个Node结构：

• 二叉树节点需要存储int类型节点值、左右孩子指针
• 链式队列的节点需要存储Node*类型的二叉树节点地址，还要维护指向队列下一个节点的指针，二者结构完全不同，无法复用。

除此之外现有代码还存在几处语法和逻辑错误：

• enqueue成员函数实现时未添加Queue::类作用域限定符，编译器会将其识别为全局函数
• 链式队列不存在rear++的指针操作，入队需要修改节点的next指针完成链接
• 字符串"Overflow!缺少闭合双引号，存在语法错误
• dequeue函数返回值定义为int，和实际需要返回的二叉树节点指针类型不匹配

1. 拆分两类节点定义 #

分别定义二叉树节点、链式队列节点结构，从根源解决类型不匹配问题：

#include<iostream>
using namespace std;

// 二叉树节点
class BiTNode{
public:
    int data;
    BiTNode *lchild, *rchild;
    BiTNode(int val):data(val), lchild(nullptr), rchild(nullptr){}
};

// 链式队列节点，专门存储二叉树节点指针
class QNode{
public:
    BiTNode* data;
    QNode* next;
    QNode(BiTNode* p):data(p), next(nullptr){}
};

2. 补全Queue类的正确实现 #

调整队列前后指针类型为QNode，修正入队、出队方法的类型匹配问题：

class Queue{
private:
    QNode *front, *rear;
public:
    Queue();
    void enqueue(BiTNode* x);
    BiTNode* dequeue();
    bool isEmpty();
};

Queue::Queue() {
    front = rear = nullptr;
}

void Queue::enqueue(BiTNode *x){
    QNode *t = new QNode(x);
    if(t == nullptr){
        cout << "Overflow!" << endl;
        return;
    }
    // 队空时头尾指针都指向新节点
    if(front == nullptr){
        front = rear = t;
    }else{
        rear->next = t;
        rear = t;
    }
}

BiTNode* Queue::dequeue(){
    if(front == nullptr){
        cout << "Underflow!" << endl;
        return nullptr;
    }
    QNode* p = front;
    BiTNode* res = p->data;
    front = front->next;
    // 出队后队空时，尾指针置空避免野指针
    if(front == nullptr){
        rear = nullptr;
    }
    delete p;
    return res;
}

bool Queue::isEmpty(){
    return front == nullptr;
}

3. 基于队列实现前序遍历 #

队列是先进先出结构，要实现前序（根-左-右）的遍历顺序，入队时需要先放右孩子、再放左孩子，保证出队时左孩子优先被访问：

void preOrderTraverse(BiTNode* root){
    if(root == nullptr) return;
    Queue q;
    q.enqueue(root);
    while(!q.isEmpty()){
        BiTNode* cur = q.dequeue();
        cout << cur->data << " ";
        // 右孩子先入队
        if(cur->rchild){
            q.enqueue(cur->rchild);
        }
        // 左孩子后入队
        if(cur->lchild){
            q.enqueue(cur->lchild);
        }
    }
}

// 测试示例
int main(){
    // 构造测试二叉树
    BiTNode* root = new BiTNode(1);
    root->lchild = new BiTNode(2);
    root->rchild = new BiTNode(3);
    root->lchild->lchild = new BiTNode(4);
    root->lchild->rchild = new BiTNode(5);
    preOrderTraverse(root); // 输出：1 2 4 5 3
    return 0;
}

注：常规前序遍历优先使用栈实现（深度优先逻辑），用队列实现属于特殊模拟写法，层序遍历才是队列的典型应用场景。

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