二叉树的遍历如果使用递归调用基本没什么问题，这里主要是讲如何使用非递归方法实现二叉树的遍历。

由于递归调用程序实际上使用了栈来保存方法中的变量值，在非递归遍历的方法中我们需要基于栈的方法。先来看看这个方法

 

01	/// <summary>

02	/// 非递归中序遍历二叉树

03	/// </summary>

04	/// <param name="root"></param>

05	static void InOrderTraverse(BinaryTreeNode root)

06

{

07	BinaryTreeNode temp = root;

08	Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();

09	stack.Push(root);

10	while (stack.Count > 0)

11

{

12	while (temp != null)

13

{

14	temp = temp.left;

15	stack.Push(temp);

16

}

17	stack.Pop();

18	//如果为0证明这时右边节点为null

19	if (stack.Count > 0)

20

{

21	temp = stack.Pop();

22	Console.WriteLine(temp.data);

23	temp = temp.right;

24	stack.Push(temp);

25

}

26

}

27

}

节点temp在这里是起一个标识的作用，首先沿根节点往左下方进行查找，将存在的节点压入栈，里面的那个while循环结束后栈的最顶端一定是一个null，所以栈pop一下，然后这时进行读取操作，读取后压入读取节点的右子节点，进入下一个while循环，temp指向右子节点。

在这里使用栈能保证左边子节点访问后找到父节点，父节点访问后也弹出栈，将右子节点压入。这里右子节点的压入和前面一部分是对应的，保证stack.Pop()这句语句的正确性。如果我们不想在栈中压入多余的那个null这时该怎么办呢？将程序改成这样

 

01	/// <summary>

02	/// 非递归中序遍历二叉树

03	/// </summary>

04	/// <param name="root"></param>

05	static void InOrderTraverse2(BinaryTreeNode root)

06

{

07	BinaryTreeNode temp = root.left;

08	Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();

09	stack.Push(root);

10	while (stack.Count > 0 || temp != null)

11

{

12	while (temp != null)

13

{

14	stack.Push(temp);

15	temp = temp.left;

16

}

17	temp = stack.Pop();

18	Console.WriteLine(temp.data);

19	temp = temp.right;

20

}

21

}

只有确定是非null才将节点压入栈，但是这里会有一个问题，当temp指向根节点的右节点的时候，栈是空的，我们需要在while循环处多加一个判断，如果temp是null证明右节点不存在，循环结束。

到这里，程序基本上已经比较完美了，不过我还是要在这里折腾一下。

while循环中的while循环的条件是temp是否为null,所以，我可以用一个if/else来换一下

 

01	static void InOrderTraverse3(BinaryTreeNode root)

02

{

03	BinaryTreeNode temp = root.left;

04	Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();

05	stack.Push(root);

06	while (stack.Count > 0 || temp != null)

07

{

08	if (temp != null)

09

{

10	stack.Push(temp);

11	temp = temp.left;

12

}

13

else

14

{

15	temp = stack.Pop();

16	Console.WriteLine(temp.data);

17	temp = temp.right;

18

}

19

}

20

}

呵呵，有意思吧。编程真奇妙~

上面三个都是二叉树的非递归中序遍历方法，非递归先序遍历和中序差不多，开始从上往下把节点入栈的时候对节点进行操作就行了，比如第二个的中序遍历改成先序遍历就是

 

01	/// <summary>

02	/// 非递归先序遍历二叉树

03	/// </summary>

04	/// <param name="root"></param>

05	static void PreOrderTraverse(BinaryTreeNode root)

06

{

07	BinaryTreeNode temp = root.left;

08	Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();

09	Console.WriteLine(root.data);

10	stack.Push(root);

11	while (stack.Count > 0 || temp != null)

12

{

13	while (temp != null)

14

{

15	Console.WriteLine(temp.data);

16	stack.Push(temp);

17	temp = temp.left;

18

}

19	temp = stack.Pop();

20	temp = temp.right;

21

}

22

}

其他的几种对着中序改一下就行了

下面来讲一讲后序遍历，后序遍历由于遍历父节点是在遍历子节点之后，而且左节点和右节点遍历后的行为不一样，所以需要用变量来记录前一次访问的节点，根据前一次节点和现在的节点的关系来确定具体执行什么操作

 

01	static void PostOrderTraversa1(BinaryTreeNode root)

02

{

03	Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();

04	stack.Push(root);

05	BinaryTreeNode prev = null;

06	BinaryTreeNode curr = null;

07	while (stack.Count > 0)

08

{

09	curr = stack.Peek();

10	if (prev == null || prev.left == curr || prev.right == curr)

11

{

12	if (curr.left != null)

13

{

14	stack.Push(curr.left);

15

}

16	else if (curr.right != null)

17

{

18	stack.Push(curr.right);

19

}

20

else

21

{

22	Console.WriteLine(curr.data);

23	stack.Pop();

24

}

25

}

26	else if (curr.left == prev)

27

{

28	if (curr.right != null)

29

{

30	stack.Push(curr.right);

31

}

32

else

33

{

34	Console.WriteLine(curr.data);

35	stack.Pop();

36

}

37

}

38	else if (curr.right == prev)

39

{

40	Console.WriteLine(curr.data);

41	stack.Pop();

42

}

43	prev = curr;

44

}

45

}

 

01	static void PostOrderTraversa2(BinaryTreeNode root)

02

{

03	Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();

04	stack.Push(root);

05	BinaryTreeNode prev = null;

06	BinaryTreeNode curr = null;

07	while (stack.Count > 0)

08

{

09	curr = stack.Peek();

10	if (prev == null || prev.left == curr || prev.right == curr)

11

{

12	if (curr.left != null)

13	stack.Push(curr.left);

14	else if (curr.right != null)

15	stack.Push(curr.right);

16

}

17	else if (curr.left == prev)

18

{

19	if (curr.right != null)

20	stack.Push(curr.right);

21

}

22

else

23

{

24	Console.WriteLine(curr.data);

25	stack.Pop();

26

}

27	prev = curr;

28

}

29

}

 

01	/// <summary>

02

/// 使用双栈

03	/// </summary>

04	/// <param name="root"></param>

05	static void PostOrderTraversa3(BinaryTreeNode root)

06

{

07	Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();

08	Stack<BinaryTreeNode> output = new Stack<BinaryTreeNode>();

09	stack.Push(root);

10	BinaryTreeNode curr = null;

11	while (stack.Count > 0)

12

{

13	curr = stack.Pop();

14	output.Push(curr);

15	if (curr.left != null)

16	stack.Push(curr.left);

17	if (curr.right != null)

18	stack.Push(curr.right);

19

}

20	while (output.Count > 0)

21

{

22	Console.WriteLine(output.Peek().data);

23	output.Pop();

24

}

25

}

只所以保留这个文章是因为其中体现了非递归的特点。可以有效的节约栈资源。提高程序的运行效率。