二叉树遍历（二叉树遍历的算法思想）

二叉树遍历（二叉树遍历的算法思想）

前言

使用C#实现一个二叉树及其基本操作, 配合xunit来做单元测试; 所以数据结构的定义和算法均使用C#实现;

概念

二叉树或为空树, 或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成;

二叉树的遍历

二叉树遍历的递归算法比较简洁, 思路比较清晰, 但是非递归的版本, 个人觉得有点难度, 我最开始看的北大一个课程中的二叉树的非递归算法, 思路很巧妙, 但是不是那么容易想到的, 后来我自己思考了一段时间, 实现了我自己版本的非递归遍历算法;

这里我用xunit做的单元测试来验证算法, 测试代码可能不是很规范...

数据结构的定义:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

public class BinaryTree

{

public T Value { get; set; }

public BinaryTree Left { get; set; }

public BinaryTree Right { get; set; }

public BinaryTree() : this(default, null, null)

{

}

public BinaryTree(

T value, BinaryTree left = null,

BinaryTree right = null)

{

Left = left;

Right = right;

Value = value;

}

...

}

前序遍历

递归版本

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

///

/// 先序遍历

///

/// 树根

/// 树的层树

/// 委托, 期望对当前节点执行的操作

protected static void PreOrderTraversal(

BinaryTree node, int depth,

Action, int> action)

{

action.Invoke(node, depth);

if (node.Left != null)

PreOrderTraversal(node.Left, depth + 1, action);

if (node.Right != null)

PreOrderTraversal(node.Right, depth + 1, action);

}

测试代码:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

[Fact]

public void PreOrderTraversalTest()

{

StringBuilder sb = new StringBuilder();

string result = null;

foreach (var d in _data)

{

d.Item1.PreOrderTraversal(

(n, l) => sb.Append($"{n.Value} "));

result = sb.ToString().TrimEnd();

Assert.Equal(result, d.Item2);

sb.Clear();

}

}

非递归版本

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

///

/// 二叉树前序遍历非递归版本

///

/// 委托, 期望对当前节点执行的操作

public void PreOrderTraversalWithoutRecusion2(

Action, int> action)

{

Stack stack = new Stack();

NodeWrapper wrapper = new NodeWrapper(this, true);

stack.Push(wrapper);

while(stack.Count > 0)

{

wrapper = stack.Pop();

action(wrapper.Node, 1);

if(wrapper.Node.Right != null)

stack.Push(new NodeWrapper(wrapper.Node.Right, true));

if((wrapper.Node.Left != null) && wrapper.FromLeft)

stack.Push(new NodeWrapper(wrapper.Node.Left, true));

else if(stack.Count > 0 && wrapper.Node.Right != null) stack.Peek().FromLeft = false;

}

}

测试代码类似非递归版本, 这里为了节省篇幅就不贴了;

中序遍历

递归版本

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

///

/// 中序遍历

///

/// 树根

/// 树的层树

/// 委托, 期望对当前节点执行的操作

protected static void InOrderTraversal(

BinaryTree node, int level,

Action, int> action)

{

if (node.Left != null)

InOrderTraversal(node.Left, level + 1, action);

action.Invoke(node, level);

if (node.Right != null)

InOrderTraversal(node.Right, level + 1, action);

}

测试代码:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

[Fact]

public void InOrderTraversalTest()

{

StringBuilder sb = new StringBuilder();

string result = null;

foreach (var d in _data)

{

d.Item1.InOrderTraversal(

(n, l) => sb.Append($"{n.Value} "));

result = sb.ToString().TrimEnd();

Assert.Equal(result, d.Item3);

sb.Clear();

}

}

非递归版本

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

///

/// 自定义类代替Tuple, 实现不递归的中序遍历, 使用Tuple会导致性能问题

/// (当需要修改栈顶元素的成员变量时, 无法修改成员, 只能先出栈->重新创建对象->再入栈)!!!

///

///

public void InOrderTraversalWithoutRecusion3(Action, int> action)

{

Stack stack = new Stack();

NodeWrapper wrapper = new NodeWrapper(this, true);

stack.Push(wrapper);

while (stack.Count > 0)

{

wrapper = stack.Pop();

if (wrapper.Node.Left != null && wrapper.FromLeft)

{

stack.Push(wrapper);

stack.Push(new NodeWrapper(wrapper.Node.Left, true));

}

else

{

action(wrapper.Node, 1); // 访问节点

if (wrapper.Node.Right != null)

stack.Push(new NodeWrapper(wrapper.Node.Right, true));

else if (stack.Count > 0)

stack.Peek().FromLeft = false;

}

}

}

测试代码类似非递归版本, 这里为了节省篇幅就不贴了;

后序遍历

递归版本

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

///

/// 后序遍历

///

/// 树根

/// 树的层树

/// 委托, 期望对当前节点执行的操作

protected static void PostOrderTraversal(

BinaryTree node, int level,

Action, int> action)

{

if (node.Left != null)

PostOrderTraversal(node.Left, level + 1, action);

if (node.Right != null)

PostOrderTraversal(node.Right, level + 1, action);

action.Invoke(node, level);

}

测试代码

1

2

3

4

5

6

7

8

9

10

11

12

13

14

[Fact]

public void PostOrderTraversalTest()

{

StringBuilder sb = new StringBuilder();

string result = null;

foreach (var d in _data)

{

d.Item1.PostOrderTraversal(

(n, l) => sb.Append($"{n.Value} "));

result = sb.ToString().TrimEnd();

Assert.Equal(d.Item4, result);

sb.Clear();

}

}

非递归版本

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

///

/// 二叉树后序遍历非递归版本

///

///

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。