分層遍歷二叉樹(shù)說(shuō)白了就是廣度優(yōu)先遍歷二叉樹(shù)，但是，題目的要求是分層打印每一層的節(jié)點(diǎn)，這樣就有一點(diǎn)難度：如何區(qū)分層呢？
其實(shí)一個(gè)比較簡(jiǎn)單的方法就是在遍歷完一層時(shí)插入一個(gè)結(jié)束標(biāo)志，這樣在訪問(wèn)到一個(gè)結(jié)束標(biāo)志時(shí)就可以知道該層結(jié)束，這樣就可以打印一個(gè)換行符。
核心代碼代碼還是廣度優(yōu)先遍歷：
數(shù)據(jù)結(jié)構(gòu)如下：
1 struct Node {
2 int data;
3 Node *left;
4 Node *right;
5 };
6
1 void visit_by_level(Node *root) {
2 Node *tmp;
3 if (root == NULL) {
4 return;
5 }
6 std::queue<Node *> q;
7 q.push(root);
8 q.push(NULL);
9 while (!q.empty()) {
10 tmp = q.front();
11 q.pop();
12 if (tmp == NULL) {
13 printf("\n");
14 if (!q.empty()) {
15 q.push(NULL);
16 continue;
17 } else {
18 break;
19 }
20 }
21 printf("%d ", tmp->data);
22 if (tmp->left) {
23 q.push(tmp->left);
24 }
25 if (tmp->right) {
26 q.push(tmp->right);
27 }
28 }
29 }
如果要只打印某一層的節(jié)點(diǎn)則，只需要對(duì)行結(jié)束標(biāo)志計(jì)數(shù)即可：
1 void print_at_level(Node *root, int level) {
2 Node *tmp;
3 int count = 1;
4 if (root == NULL) {
5 return;
6 }
7 std::queue<Node *> q;
8 q.push(root);
9 q.push(NULL);
10 while (!q.empty()) {
11 tmp = q.front();
12 q.pop();
13 if (tmp == NULL) {
14 count++;
15 if (count == level + 1) {
16 printf("\n");
17 }
18 if (!q.empty()) {
19 q.push(NULL);
20 continue;
21 } else {
22 break;
23 }
24 }
25 if (count == level) {
26 printf("%d ", tmp->data);
27 }
28 if (tmp->left) {
29 q.push(tmp->left);
30 }
31 if (tmp->right) {
32 q.push(tmp->right);
33 }
34 }
35 }
代碼比較簡(jiǎn)單，就不多講解了
posted on 2012-09-02 22:36
myjfm 閱讀(579)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
算法基礎(chǔ)