【C++二叉搜索树】采用STL实现广度遍历时遇见的问题

首先是二叉树结点类型定义

 typedef struct node {
    ElemType data;
    struct node* lchild;
    struct node* rchild;
}*BST,BSTree;

此为一开始的广度遍历代码：

 void Level(BST root)
{
    queue<BSTree> Q;
    BST temp;
    if (!root)
        return;
    Q.push(*root);
    while (Q.size()>0)
    {
        temp = &(Q.front());
        Q.pop();
        cout << temp->data;
        if (temp->lchild)
            Q.push(*(temp->lchild));
        if (temp->rchild)
            Q.push(*(temp->rchild));
    }
}

遍历结果总是缺少子树或者重复包含，后改为以下代码：

正常打印

void Level(BST root)
{
    queue<BSTree> Q;
    BST temp;
    BSTree P;
    if (!root)
        return;
    Q.push(*root);
    while (Q.size()>0)
    {
        P = Q.front();
        temp = &P;
        Q.pop();
        cout << temp->data;
        if (temp->lchild)
            Q.push(*(temp->lchild));
        if (temp->rchild)
            Q.push(*(temp->rchild));
    }
} 

怀疑问题出在#include中的pop()函数，求解答，Orz。

http://www.tuicool.com/articles/u2qEZz

没看出哪里有问题，复现了一下你的代码，可以正常输出

#include <iostream>
#include <queue>
using namespace std;

typedef struct node {
    int data;
    struct node* lchild;
    struct node* rchild;
}*BST, BSTree;

void level(BST root)
{
    queue<BSTree> Q;
    BST temp;
    if(!root)
        return;
    Q.push(*root);
    while(Q.size() > 0)
    {
        temp = &(Q.front());
        Q.pop();
        cout << temp->data << " ";
        if(temp->lchild)
            Q.push(*(temp->lchild));
        if(temp->rchild)
            Q.push(*(temp->rchild));
    }
}

int main()
{
    BST root = new BSTree();
    BST one = new BSTree();
    BST two = new BSTree();
    BST three = new BSTree();
    BST four = new BSTree();
    BST five = new BSTree();
    BST six = new BSTree();
    BST seven = new BSTree();
    root->data = 0;
    one->data = 1;
    two->data = 2;
    three->data = 3;
    four->data = 4;
    five->data = 5;
    six->data = 6;
    seven->data = 7;
    root->lchild = one;
    root->rchild = two;
    one->lchild = three;
    one->rchild = four;
    two->lchild = five;
    two->rchild = six;
    three->lchild = seven;
    three->rchild = NULL;
    four->lchild = NULL;
    four->rchild = NULL;
    five->lchild = NULL;
    five->rchild = NULL;
    six->lchild = NULL;
    six->rchild = NULL;
    seven->lchild = NULL;
    seven->rchild = NULL;
    level(root);

    return 0;
}

http://blog.csdn.net/tutuxs/article/details/52622777