分层遍历二叉树说白了就是广度优先遍历二叉树，但是，题目的要求是分层打印每一层的节点，这样就有一点难度：如何区分层呢？
其实一个比较简单的方法就是在遍历完一层时插入一个结束标志，这样在访问到一个结束标志时就可以知道该层结束，这样就可以打印一个换行符。
核心代码代码还是广度优先遍历：
数据结构如下：
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 }
如果要只打印某一层的节点则，只需要对行结束标志计数即可：
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 }
代码比较简单，就不多讲解了
posted on 2012-09-02 22:36
myjfm 阅读(563)
评论(0) 编辑 收藏 引用 所属分类:
算法基础