3.後序遍歷
若二叉樹為非空，則過程為：
（1）按後序遍歷左子樹。
（2）按後序遍歷右子樹
（3）訪問根結點。
圖6.13中，先序遍歷就是把標號為(3)的結點按搜索路徑訪問的先後次序連接起來，得出結果為：DEBFCA。
【例6-1 BinaryTreeNode.cs】二叉樹結點類
1 using System;
2 public class Node
3 {
4 //成員變量
5 private object _data; //數據
6 private Node _left; //左孩子
7 private Node _right; //右孩子
8 public object Data
9 {
10 get { return _data; }
11 }
12 public Node Left //左孩子
13 {
14 get { return _left; }
15 set { _left = value; }
16 }
17 public Node Right //右孩子
18 {
19 get { return _right; }
20 set { _right = value; }
21 }
22 //構造方法
23 public Node(object data)
24 {
25 _data = data;
26 }
27 public override string ToString()
28 {
29 return _data.ToString();
30 }
31 }
32
Node類專門用於表示二叉樹中的一個結點，它很簡單，只有三個屬性：Data表示結點中的數據；Left表示這個結點的左孩子，它是Node類型；Right表示這個結點的右孩子，它也是Node類型。
【例6-1 BinaryTree.cs】二叉樹集合類
1 using System;
2 public class BinaryTree
3 { //成員變量
4 private Node _head; //頭指針
5 private string cStr; //用於構造二叉樹的字符串
6 public Node Head //頭指針
7 {
8 get { return _head; }
9 }
10 //構造方法
11 public BinaryTree(string constructStr)
12 {
13 cStr = constructStr;
14 _head = new Node(cStr[0]); //添加頭結點
15 Add(_head, 0); //給頭結點添加孩子結點
16 }
17 private void Add(Node parent, int index)
18 {
19 int leftIndex = 2 * index + 1; //計算左孩子索引
20 if (leftIndex < cStr.Length) //如果索引沒超過字符串長度
21 {
22 if (cStr[leftIndex] != '#') //'#'表示空結點
23 { //添加左孩子
24 parent.Left = new Node(cStr[leftIndex]);
25 //遞歸調用Add方法給左孩子添加孩子節點
26 Add(parent.Left, leftIndex);
27 }
28 }
29 int rightIndex = 2 * index + 2;
30 if (rightIndex < cStr.Length)
31 {
32 if (cStr[rightIndex] != '#')
33 { //添加右孩子
34 parent.Right = new Node(cStr[rightIndex]);
35 //遞歸調用Add方法給右孩子添加孩子節點
36 Add(parent.Right, rightIndex);
37 }
38 }
39 }
40 public void PreOrder(Node node) //先序遍歷
41 {
42 if (node != null)
43 {
44 Console.Write(node.ToString()); //打印字符
45 PreOrder(node.Left); //遞歸
46 PreOrder(node.Right); //遞歸
47 }
48 }
49 public void MidOrder(Node node) //中序遍歷
50 {
51 if (node != null)
52 {
53 MidOrder(node.Left); //遞歸
54 Console.Write(node.ToString()); //打印字符
55 MidOrder(node.Right); //遞歸
56 }
57 }
58 public void AfterOrder(Node node) //後繼遍歷
59 {
60 if (node != null)
61 {
62 AfterOrder(node.Left); //遞歸
63 AfterOrder(node.Right); //遞歸
64 Console.Write(node.ToString()); //打印字符
65 }
66 }
67 }
68
