C#與數據結構--二叉樹的遍歷(5)

6.3.2二叉樹的寬度優先遍歷

之前所講述的二叉樹的深度優先遍歷的搜索路徑是首先搜索一個結點的所有子孫結點，再搜索這個結點的兄弟結點。是否可以先搜索所有兄弟和堂兄弟結點再搜索子孫結點呢？

由於二叉樹結點分屬不同的層次，因此可以從上到下、從左到右依次按層訪問每個結點。它的訪問順序正好和之前所述二叉樹順序存儲結構中的結點在數組中的存放順序相吻合。如圖6.13中的二叉樹使用寬度優先遍歷訪問的順序為：ABCDEF。

這個搜索過程不再需要使用遞歸，但需要借助隊列來完成。

（1）將根結點壓入隊列之中，開始執行步驟(2)。

（2）若隊列為空，則結束遍歷操作，否則取隊頭結點D。

（3）若結點D的左孩子結點存在，則將其左孩子結點壓入隊列。

（4）若結點D的右孩子結點存在，則將其右孩子結點壓入隊列，並重復步驟(2)。

【例6-2 BinaryTreeNode.cs.cs】二叉樹結點類，使用例6-1同名文件。

【例6-2 LevelOrderBinaryTree.cs】包含寬度優先遍歷方法的二叉樹集合類

打開例6-1的【BinaryTree.cs】文件，在BinaryTree類中添加如入方法後另存為LevelOrderBinaryTree.cs文件。

1     public void LevelOrder() //寬度優先遍歷
 2     {
 3         Queue queue = new Queue(); //聲明一個隊例
 4         queue.Enqueue(_head); //把根結點壓入隊列
 5         while (queue.Count > 0) //只要隊列不為空
 6         {
 7             Node node = (Node)queue.Dequeue(); //出隊
 8             Console.Write(node.ToString()); //訪問結點
 9             if (node.Left != null) //如果結點左孩子不為空
10             {   //把左孩子壓入隊列
11                 queue.Enqueue(node.Left);
12             }
13             if (node.Right != null) //如果結點右孩子不為熔
14             {   //把右孩子壓入隊列
15                 queue.Enqueue(node.Right);
16             }
17         }
18     }

【例6-2 Demo6-2.cs】二叉樹寬度優先遍歷測試

1 using System;
2 class Demo6_2
3 {
4     static void Main(string[] args)
5     {   //使用字符串構造二叉樹
6         BinaryTree bTree = new BinaryTree("ABCDE#F");
7         bTree.LevelOrder();
8     }
9 }