找了下先序遍歷二叉樹C# 實現貌似沒有 順手些了一個
大致思路是：
傳入根節點，然後依次循環其子節點推入到棧中，
當推入的節點沒有子節點的時候（葉子）或者所有子節點均已經遍歷過後（上一次遍歷的節點是該節點的右子節點），再依次退出棧。
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5 using System.Threading.Tasks;
6
7 namespace ConsoleApplication5
8 {
9 class Program
10 {
11 static void Main(string[] args)
12 {
13 Node treeRoot = CreateTree();
14 scanTree(treeRoot);
15 }
16
17 private static void scanTree(Node treeRoot)
18 {
19 List<Node> list = new List<Node>();
20 list.Add(treeRoot);
21 Node point = treeRoot;
22 Write(treeRoot);
23 while (true)
24 {
25 if (!list.Contains(point))
26 { //上一輪是移除的操作
27 if (treeRoot.leftSon == point)
28 {//移除的是左結點
29 if (treeRoot.rightSon != null)
30 {
31 treeRoot = treeRoot.rightSon;
32 list.Add(treeRoot);
33 Write(treeRoot);
34 point = treeRoot;
35 continue;
36 }
37 list.Remove(treeRoot);
38 if (list.Count == 0)
39 {
40 break;
41 }
42 point = treeRoot;
43 treeRoot = list[list.Count - 1];
44 }
45 else
46 {//移除的是右結點
47 list.Remove(treeRoot);
48 if (list.Count == 0)
49 {
50 break;
51 }
52 point = treeRoot;
53 treeRoot = list[list.Count - 1];
54 }
55 continue;
56 }
57
58 if (treeRoot.leftSon != null)
59 {
60 treeRoot = treeRoot.leftSon;
61 Write(treeRoot);
62 list.Add(treeRoot);
63 point = treeRoot;
64 continue;
65 }
66 if (treeRoot.rightSon != null)
67 {
68 treeRoot = treeRoot.rightSon;
69 Write(treeRoot);
70 point = treeRoot;
71 list.Add(treeRoot);
72 continue;
73 }
74 //當前的節點是葉子節點 if (treeRoot.leftSon == null && treeRoot.rightSon == null)
75 //{
76 list.Remove(treeRoot);
77 if (list.Count == 0)
78 {
79 break;
80 }
81 point = treeRoot;
82 treeRoot = list[list.Count - 1];
83 // }
84 }
85
86 }
87
88 public static void Write(Node node)
89 {
90 Console.WriteLine(node.Data);
91 }
92
93 private static Node CreateTree()
94 {
95 Node a = new Node("A");
96 a.leftSon = new Node("B");
97 a.rightSon = new Node("C");
98
99 a.leftSon.leftSon = new Node("D");
100 a.leftSon.rightSon = new Node("E");
101
102 a.rightSon.leftSon = new Node("F");
103 a.rightSon.rightSon = new Node("G");
104
105 a.leftSon.leftSon.leftSon = new Node("H");
106 a.leftSon.leftSon.rightSon = new Node("I");
107 return a;
108 }
109 }
110
111 class Node
112 {
113 public string Data { get; set; }
114 public Node leftSon { get; set; }
115 public Node rightSon { get; set; }
116
117 public Node(string data)
118 {
119 Data = data;
120 }
121 }
122 }
