原文链接：http://blog.csdn.net/flyinghearts/archive/2010/05/25/5624081.aspx
3.10 分层遍历二叉树
看到Milo写的这篇文章，又翻了下书，发现书的代码（P253）有个瑕疵，每个节点值后面都会显示一个空格，如果将间隔字符改为“-”，输出的每行最后都有一个“-”，不能达到要求。不过，只要将 cout << vec[cur] -> data << " ";
这行改为：
if (cur==last-1) cout << vec[cur] -> data << "/n";
else cout << vec[cur] -> data << " ";
即可修正这个问题。
书上的代码用了两个while循环，可以精简为一个。
思路：保存每层的最后一个节点位置（取节点的地址或在容器内的位置），当遍历到该位置时，获取下一层最后一个节点的位置，如果这两个位置相同，说明已经遍历完全部节点，否则开始下一层的遍历。
由于不知道树的节点数，很多情况下，容器采用deque比采用vector性能更佳，因为避免了申请内存后对原数据的拷贝。另外，再考虑到deque的数组下标访问要比采用迭代器访问慢很多，最好采用迭代器来访问内部数据。
- struct Node {
- Node *left;
- Node *right;
- int data;
- };
- void print_tree_bfs_d(Node* root) {
- if (root==NULL) return;
- deque<Node*> tree;
- tree.push_back(root);
- deque<Node*>::iterator low=tree.begin(),last=tree.begin();
- Node *node=root;
- while (1){
- if (node->left) tree.push_back(node->left);
- if (node->right) tree.push_back(node->right);
- if (low!=last){
- cout << node->data << " ";
- }else{
- cout<< node->data << "/n";
- if (last==tree.end()-1) break;
- last=tree.end()-1;
- }
- node=*++low;
- }
- cout<< "/n";
- }
上面的代码，保留了树的所有全部节点，稍做修改（比如用一个数组记录每层的最后一个节点的位置），可以查询某层的所有节点。如果不需要保存中间结果，可以修改为：
- void print_tree_bfs_dq(Node* root) {
- if (root==NULL) return;
- deque<Node*> tree;
- tree.push_back(root);
- deque<Node*>::iterator low=tree.begin();
- Node *node=root, *last=root;