用递归方法对二叉树进行层次遍历

      在这里看到了这个题。层次遍历是用队列，一级一级地入队列然后输出。而用递归的话，我首先想到是用两个栈来模拟队列，在递归遍历二叉树的过程中入栈，然后最后一次性出栈。但仔细思考后发现无法做到层次遍历。在这里看到了正确的方法。

     主要代码如下:

void PrintNodeAtLevel(BiTree T,int level)
 {
     // 空树或层级不合理
     if (NULL == T || level < 1 )
         return;

     if (1 == level)
     {
         cout << T->data << "  ";
         return;
     }

     // 左子树的 level - 1 级
     PrintNodeAtLevel(T->leftChild, level - 1);

     // 右子树的 level - 1 级
     PrintNodeAtLevel(T->rightChild, level - 1);
 }


 void LevelTraverse(BiTree T)
 {
     if (NULL == T)
         return;

     int depth = Depth(T);

     int i;
     for (i = 1; i <= depth; i++)
     {
         PrintNodeAtLevel(T, i);
         cout << endl;
     }
 }

      这个算法先求出根结点的高度，depth=高度+1。在函数PrintNodeAtLevel中，当且仅当level==1时才进行打印。举个例子:

         1 

    2        3

4     5    6   7

     这棵树的根的高度是2,depth=3。然后，在LevelTraverse函数中，level从1开始，这会打印出1；之后level=2,进入PrintNodeAtLevel(T->leftChild,  level - 1)函数和PrintNodeAtLevel(T->rightChild, level - 1)，level又等于1，就打印出2，3。以此类推，整棵树就按层打印出来了。

     参考资料(即此递归算法的来源):http://blog.csdn.net/stpeace/article/details/8138458

      如果你觉得我的文章对你有帮助，请赞一下，非常感谢!