二叉樹遍歷

前言

使用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);
        }

    }
}

測試代碼類似非遞歸版本, 這裡為了節省篇幅就不貼了;