雁过无痕

《编程之美》读书笔记16： 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的数组下标访问要比采用迭代器访问慢很多，最好采用迭代器来访问内部数据。

代码一
 1
 2struct Node {
 3  Node *left;
 4  Node *right;
 5  int data;
 6};
 7void print_tree_bfs_d(Node* root) {
 8  if (root==NULL) return;
 9  deque<Node*> tree;
10  tree.push_back(root);
11  deque<Node*>::iterator low=tree.begin(),last=tree.begin();
12  Node *node=root;
13  while (1){
14      if (node->left)  tree.push_back(node->left);
15      if (node->right) tree.push_back(node->right);
16    if (low!=last){
17      cout << node->data << " ";
18    }else{
19      cout<< node->data << "\n";
20      if (last==tree.end()-1) break;
21      last=tree.end()-1;
22    }
23    node=*++low;
24  }
25  cout<< "\n";
26}
27
28

上面的代码，保留了树的所有全部节点，稍做修改（比如用一个数组记录每层的最后一个节点的位置），可以查询某层的所有节点。如果不需要保存中间结果，可以修改为：

代码二
 1
 2void print_tree_bfs_dq(Node* root) {
 3  if (root==NULL) return;
 4  deque<Node*> tree;
 5  tree.push_back(root);
 6  Node *node=root, *last=root;
 7  while (1){
 8    node=tree.front();
 9    tree.pop_front();
10      if (node->left)  tree.push_back(node->left);
11      if (node->right) tree.push_back(node->right);
12    if (node!=last){
13      cout << node->data << "-";
14    }else{
15      cout<< node->data << "\n";
16      if (tree.empty()) break;
17      last=tree.back();
18    }
19  }
20  cout<< "\n";
21}
22
23

当然也可以用queue（queue只是对deque的封装）。

对问题2，上面的代码只要做稍微修改，只在遍历到所要求的层才输出，输出后直接返回就可以了。