-
C#教程之二叉树遍历
本站最新发布 C#从入门到精通
试听地址 https://www.xin3721.com/eschool/CSharpxin3721/
试听地址 https://www.xin3721.com/eschool/CSharpxin3721/
前言
使用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<T>
{
public T Value { get; set; }
public BinaryTree<T> Left { get; set; }
public BinaryTree<T> Right { get; set; }
public BinaryTree() : this(default, null, null)
{
}
public BinaryTree(
T value, BinaryTree<T> left = null,
BinaryTree<T> right = null)
{
Left = left;
Right = right;
Value = value;
}
...
}
前序遍历
递归版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/// <summary>
/// 先序遍历
/// </summary>
/// <param name="node">树根</param>
/// <param name="depth">树的层树</param>
/// <param name="action">委托, 期望对当前节点执行的操作</param>
protected static void PreOrderTraversal(
BinaryTree<T> node, int depth,
Action<BinaryTree<T>, 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<string>(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
/// <summary>
/// 二叉树前序遍历非递归版本
/// </summary>
/// <param name="action">委托, 期望对当前节点执行的操作</param>
public void PreOrderTraversalWithoutRecusion2(
Action<BinaryTree<T>, int> action)
{
Stack<NodeWrapper> stack = new Stack<NodeWrapper>();
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
/// <summary>
/// 中序遍历
/// </summary>
/// <param name="node">树根</param>
/// <param name="level">树的层树</param>
/// <param name="action">委托, 期望对当前节点执行的操作</param>
protected static void InOrderTraversal(
BinaryTree<T> node, int level,
Action<BinaryTree<T>, 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<string>(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
/// <summary>
/// 自定义类代替Tuple, 实现不递归的中序遍历, 使用Tuple会导致性能问题
/// (当需要修改栈顶元素的成员变量时, 无法修改成员, 只能先出栈->重新创建对象->再入栈)!!!
/// </summary>
/// <param name="action"></param>
public void InOrderTraversalWithoutRecusion3(Action<BinaryTree<T>, int> action)
{
Stack<NodeWrapper> stack = new Stack<NodeWrapper>();
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
/// <summary>
/// 后序遍历
/// </summary>
/// <param name="node">树根</param>
/// <param name="level">树的层树</param>
/// <param name="action">委托, 期望对当前节点执行的操作</param>
protected static void PostOrderTraversal(
BinaryTree<T> node, int level,
Action<BinaryTree<T>, 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<string>(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
/// <summary>
/// 二叉树后序遍历非递归版本
/// </summary>
/// <param name="action"></param>
栏目列表
最新更新
Python 中如何实现参数化测试?
Appium移动端测试--基础预热
自定义404页面
python redis模块详解
python爬虫--图片懒加载
Python抓取豆瓣电影top250!
Tornado—添加请求头允许跨域请求访问
pycharm设置开发模板/字体大小/背景颜色(
python爬虫公众号所有信息,并批量下载公
docker系列之一:初见docker
.Net Standard(.Net Core)实现获取配置信息
Linux PXE + Kickstart 自动装机
Shell 编程 基础
Shell 编程 条件语句
CentOS8-网卡配置及详解
Linux中LVM逻辑卷管理
1.数码相框-相框框架分析(1)
Ubuntu armhf 版本国内源
Linux中raid磁盘阵列
搭建简易网站
mysql 安装了最新版本8.x版本后的报错:
Mysql空间数据&空间索引(spatial)
如何远程连接SQL Server数据库的图文教程
复制SqlServer数据库的方法
搜索sql语句
sql中返回参数的值
sql中生成查询的模糊匹配字符串
数据定义功能
数据操作功能
将Session值储存于SQL Server中