多平台统一管理软件接口，如何实现多平台统一管理软件接口
252
2022-06-22
二叉树遍历（二叉树遍历算法）
前言
使用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
public BinaryTree
public BinaryTree() : this(default, null, null)
{
}
public BinaryTree(
T value, BinaryTree
BinaryTree
{
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
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
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
{
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
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
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
{
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
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
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小时内删除侵权内容。
相关文章
发表评论
暂时没有评论，来抢沙发吧~