Massive Algorithms: 《编程之美：分层遍历二叉树》的另外两个实现 - Milo Yip

给定一棵二叉树，要求按分层遍历该二叉树，即从上到下按层次访问该二叉树(每一层将单独输出一行)，每一层要求访问的顺序为从左到右，并将节点依次编号。

利用了两个队列，一个储存本层的节点，另一个储存下层的节点。遍历本层的节点，把其子代节点排入下层队列。本层遍历完毕后，就可换行，并交换两个队列。

void PrintNodeByLevel(Node* root) {

    deque<Node*> Q1, Q2;

    Q1.push_back(root);

    do {

        do {

            Node* node = Q1.front();

            Q1.pop_front();

            cout << node->data << " ";

            if (node->pLeft)

                Q2.push_back(node->pLeft);

            if (node->pRight)

                Q2.push_back(node->pRight);

        } while (!Q1.empty());

        cout << endl;

        Q1.swap(Q2); 

    } while(!Q1.empty());

}

是把一个结束信号放进队列里。由于使用queue<Node*>，可以插入一个空指针去表示一层的遍历结束。

void PrintNodeByLevel(Node* root) {

    queue<Node*> Q;

    Q.push(root);

    Q.push(0);

    do {

        Node* node = Q.front();

        Q.pop();

        if (node) {

            cout << node->data << " ";

            if (node->pLeft)

                Q.push(node->pLeft);

            if (node->pRight)

                Q.push(node->pRight);

}

        else if (!Q.empty()) {

            Q.push(0);

            cout << endl;

}

    } while (!Q.empty());

}

Labels