二叉树的非递归遍历
二叉树的遍历如果使用递归调用基本没什么问题,这里主要是讲如何使用非递归方法实现二叉树的遍历。
由于递归调用程序实际上使用了栈来保存方法中的变量值,在非递归遍历的方法中我们需要基于栈的方法。先来看看这个方法
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 |
} |