用遞歸方法對二叉樹進行層次遍歷

      在這裡看到了這個題。層次遍歷是用隊列，一級一級地入隊列然後輸出。而用遞歸的話，我首先想到是用兩個棧來模擬隊列，在遞歸遍歷二叉樹的過程中入棧，然後最後一次性出棧。但仔細思考後發現無法做到層次遍歷。在這裡看到了正確的方法。

     主要代碼如下:

 1 void PrintNodeAtLevel(BiTree T,int level)
 2 {
 3     // 空樹或層級不合理
 4     if (NULL == T || level < 1 )
 5         return;
 6 
 7     if (1 == level)
 8     {
 9         cout << T->data << "  ";
10         return;
11     }
12 
13     // 左子樹的 level - 1 級
14     PrintNodeAtLevel(T->leftChild,  level - 1);
15 
16     // 右子樹的 level - 1 級
17     PrintNodeAtLevel(T->rightChild, level - 1);
18 }
19 
20 
21 void LevelTraverse(BiTree T)
22 {
23     if (NULL == T)
24         return;
25 
26     int depth = Depth(T);
27 
28     int i;
29     for (i = 1; i <= depth; i++)
30     {
31         PrintNodeAtLevel(T, i);
32         cout << endl;
33     }
34 }

      這個演算法先求出根結點的高度，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。以此類推，整棵樹就按層列印出來了。