《編程之美》讀書(shū)筆記16： 3.10 分層遍歷二叉樹(shù)

看到Milo寫(xiě)的這篇文章，又翻了下書(shū)，發(fā)現(xiàn)書(shū)的代碼（P253）有個(gè)瑕疵，每個(gè)節(jié)點(diǎn)值后面都會(huì)顯示一個(gè)空格，如果將間隔字符改為“-”，輸出的每行最后都有一個(gè)“-”，不能達(dá)到要求。不過(guò)，只要將 cout << vec[cur] -> data << " ";

這行改為：

if (cur==last-1) cout << vec[cur] -> data << "\n";

else cout << vec[cur] -> data << " ";

即可修正這個(gè)問(wèn)題。

書(shū)上的代碼用了兩個(gè)while循環(huán)，可以精簡(jiǎn)為一個(gè)。

思路：保存每層的最后一個(gè)節(jié)點(diǎn)位置（取節(jié)點(diǎn)的地址或在容器內(nèi)的位置），當(dāng)遍歷到該位置時(shí)，獲取下一層最后一個(gè)節(jié)點(diǎn)的位置，如果這兩個(gè)位置相同，說(shuō)明已經(jīng)遍歷完全部節(jié)點(diǎn)，否則開(kāi)始下一層的遍歷。

由于不知道樹(shù)的節(jié)點(diǎn)數(shù)，很多情況下，容器采用deque比采用vector性能更佳，因?yàn)楸苊饬松暾?qǐng)內(nèi)存后對(duì)原數(shù)據(jù)的拷貝。另外，再考慮到deque的數(shù)組下標(biāo)訪(fǎng)問(wèn)要比采用迭代器訪(fǎng)問(wèn)慢很多，最好采用迭代器來(lái)訪(fǎng)問(wèn)內(nèi)部數(shù)據(jù)。

代碼一
 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

上面的代碼，保留了樹(shù)的所有全部節(jié)點(diǎn)，稍做修改（比如用一個(gè)數(shù)組記錄每層的最后一個(gè)節(jié)點(diǎn)的位置），可以查詢(xún)某層的所有節(jié)點(diǎn)。如果不需要保存中間結(jié)果，可以修改為：

代碼二
 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

當(dāng)然也可以用queue（queue只是對(duì)deque的封裝）。

對(duì)問(wèn)題2，上面的代碼只要做稍微修改，只在遍歷到所要求的層才輸出，輸出后直接返回就可以了。