二叉树遍历

二叉树遍历

前言

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

概念

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

二叉树的遍历

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

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

数据结构的定义:

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; } ...}

前序遍历

递归版本

/// <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);}

测试代码:

[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(); }}

非递归版本

/// <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; }}

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

中序遍历

递归版本

/// <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);}

测试代码:

[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(); }}

非递归版本

/// <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;  } }}

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

后序遍历

递归版本

/// <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);}

测试代码

[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(); }}

非递归版本

/// <summary>/// 二叉树后序遍历非递归版本/// </summary>/// <param name="action"></param>public void PostOrderTraversalWithoutRecusion2(Action<BinaryTree<T>, int> action){ Stack<NodeWrapper> stack = new Stack<NodeWrapper>(); NodeWrapper wrapper = new NodeWrapper(this, false); 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, false));  }  else  {   if(stack.Count > 0)    stack.Peek().FromLeft = true;   if (wrapper.Node.Right != null && !wrapper.FromRight)   {    wrapper.FromRight = true;    stack.Push(wrapper);    stack.Push(new NodeWrapper(wrapper.Node.Right, false));   }   else action(wrapper.Node, 1);  } }}

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