二叉树:层次遍历

编辑于 2017-01-17

* 移动设备下, 可左滑手指以查看较宽代码

我们可以设置两个队列,想象一下队列的特点,就是先进先出,首先把第0层保存在一个队列中,然后按节点访问,并把已经访问节点的左右孩子节点放在第二个队列中,当第一个队列中的所有节点都访问完成之后,交换两个节点。这样重复下去,知道所有层的节点都被访问,这样做的代价就是空间复杂度有点高。

void print_by_level_2(Tree T)
{  
    deque<tree_node_t*> q_first, q_second;  
    q_first.push_back(T);  
    while(!q_first.empty()) {  
        while (!q_first.empty()) {  
            tree_node_t *temp = q_first.front();  
            q_first.pop_front();  
            cout << temp->data << " ";  
            if (temp->lchild)  
                q_second.push_back(temp->lchild);  
            if (temp->rchild)  
                q_second.push_back(temp->rchild);  
        }  
        cout << endl;  
        q_first.swap(q_second);  
    }  
}