BinaryTree是一個二叉樹的集合類，它屬於二叉鏈表，實際存儲的信息只有一個頭結點指針（Head），由於是鏈式存儲結構，可以由Head指針出發遍歷整個二叉樹。為了便於測試及添加結點，假設BinaryTree類中存放的數據是字符類型，第5行聲明了一個字符串類型成員cStr，它用於存放結點中所有的字符。字符串由滿二叉樹的方式進行構造，空結點用‘#’號表示（參考本章“二叉樹存儲結構”這一小節中的“順序存儲結構”）。圖6.13所示的二叉樹可表示為：“ABCDE#F”。
11～16行的構造方法傳入一個構造字符串，並在Add()方法中根據這個字符串來構造二叉樹中相應的結點。需要注意，這個構造方法只用於測試。
17～39行的Add()方法用於添加結點，它的第一個參數parent表示需要添加孩子結點的雙親結點，第二個參數index表示這個雙親結點的編號（編號表示使用順序存儲結構時它在數組中的索引，請參考本章“二叉樹存儲結構”這一小節中的“順序存儲結構”）。添加孩子結點的方法是先計算孩子結點的編號，然後通過這個編號在cStr中取出相應的字符，並構造新的孩子結點用於存放這個字符，接下來遞歸調用Add()方法給孩子結點添加它們的孩子結點。注意，這個方法只用於測試。
40～48行代碼的PreOrder()方法用於先序遍歷，它的代碼跟之前所講解的先序遍歷過程完全一樣。
49～57行代碼的MidOrder()方法用於中序遍歷。
58～66行代碼的AfterOrder()方法用於後序遍歷。
以上三個方法都使用了遞歸來完成遍歷，這符合二叉樹的定義。
【例6-1 Demo6-1.cs】二叉樹深度優先遍歷測試
1 using System;
2 class Demo6_1
3 {
4 static void Main(string[] args)
5 { //使用字符串構造二叉樹
6 BinaryTree bTree = new BinaryTree("ABCDE#F");
7 bTree.PreOrder(bTree.Head); //先序遍
8 Console.WriteLine();
9 bTree.MidOrder(bTree.Head); //中序遍
10 Console.WriteLine();
11 bTree.AfterOrder(bTree.Head); //後序遍
12 Console.WriteLine();
13 }
14 }
15
運行結果：
ABDECF
DBEACF
DEBFCA
