雁過無痕

《編程之美》讀書筆記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，上面的代碼只要做稍微修改，只在遍歷到所要求的層才輸出，輸出后直接返回就可以了。