分层遍历二叉树

时间：2023-02-04 11:09:29

http://www.cnblogs.com/pangxiaodong/archive/2011/09/11/2173560.html

1. 简述

    问题一：给定一棵二叉树，要求按分层遍历该二叉树，即从上到下的层次访问该二叉树（每一层将单独输出一行），每一层要求访问的顺序为从左到右，并将节点依次编号。
    问题二：写一个函数，打印二叉树中某层次的节点（从左到右），其中根节点为第0层，函数原型为int PrintNodeAtLevel(Node* root, int level)，成功返回1，失败返回0。

2. 思路

    使用队列进行广度优先搜索，主要有一个特点，即如果第k层元素一个都没出队，那么队列中必然没有k+1层元素，而且如果第k层元素刚好都出队了，队列中只有第k+1层元素，且包含所有的k+1层元素。所以从第一层开始，把根节点入队，记录当前层节点数1，然后输出这个层得所有节点，跟新队列，然后正好队列中就只有且包含所有第2层得节点数了，依次类推直到队列为空为止。
   简述中的两个问题基本上就是一回事，第二个问题就是在第一个问题的基础上，注意判断层数，和当前层位置即可。

3. 代码

    这里给出第一个问题的代码实现。      

分层遍历二叉树
#include<iostream>
#include<deque> 
using namespace std;

struct NODE {
  NODE* pLeft;
  NODE* pRight;
int value;
};

void PrintTreeByLevel(const NODE* root) {
  deque<const NODE*> store;
int left_num;
if(!root)
return;
  store.push_back(root);
while(!store.empty()) {
    left_num = store.size(); // 当前层的节点数
    while(left_num-- > 0) {
const NODE* tmp = store.front();
      store.pop_front();
      cout << tmp->value << " ";
if(tmp->pLeft)
        store.push_back(tmp->pLeft);
if(tmp->pRight)
        store.push_back(tmp->pRight);
    }
    cout << endl;
  }
}

int main() {
  NODE* array[8];
for(int i=0; i<8; i++) {
    array[i] = new NODE;
    array[i]->value = 1 + i;
    array[i]->pLeft = array[i]->pRight = NULL;
  }
  array[0]->pLeft = array[1]; array[0]->pRight = array[2];
  array[1]->pLeft = array[3]; array[1]->pRight = NULL;
  array[2]->pLeft = array[4]; array[2]->pRight = array[5];
  array[4]->pLeft = array[6]; array[4]->pRight = array[7];
  PrintTreeByLevel(array[0]);
  ReversePrintTreeByLevel(array[0]);
  system("PAUSE");
return 0;
}
分层遍历二叉树

    输出结果为： 

    分层遍历二叉树

4. 扩展问题

    扩展问题中要求先输出最后一层，然后输出倒数第二层，···，最后输出第一层。
    第一直觉是按照前面的方法遍历的过程中，记录每层元素个数，注意遍历中只入队不出队，每层遍历是否结束，需要多设置一些计数变量。
    不过在参考中的一篇文章中，看到使用哑元素的方法，即在每层中间插入NULL，同样，遍历中也是只入队不出对，每层遍历是否结束，需要多设置一些计数变量。
    代码如下：   

分层遍历二叉树
void ReversePrintTreeByLevel(const NODE* root) {
  deque<const NODE*> store;
int index = 0; // 遍历元素和哑元素的下标
  int no = 0; // 遍历过的元素个数 
  if(!root) {
return;
  }
  store.push_back(root);  
  index = 0;
while(index < store.size()) {
    store.push_back(NULL); // 哑元素 
    while(store[index] != NULL) { // 访问当前层
      no++;
if(store[index]->pRight)
        store.push_back(store[index]->pRight);
if(store[index]->pLeft)
        store.push_back(store[index]->pLeft);
      index++;
    }
    index++;
  }
for(int i=store.size()-1; i>=0; i--) {
if(store[i] == NULL)
      cout << endl;
else {
      cout << store[i]->value << " ";
    }
  }
  cout << endl;
}
分层遍历二叉树

    合并两部分代码输出结果为：

    分层遍历二叉树


标签：

相关文章