算法与数据结构

数据结构

链表

public class Node<T>
{
    public T Value;
    public Node<T> Next;

    public Node(T value) : this(value, null) {}

    public Node(T value, Node<T> next)
    {
        Value = value;
        Next = next;
    }
}

二叉树

public class TreeNode<T>
{
    public T Value;
    public TreeNode<T> Left;
    public TreeNode<T> Right;

    public TreeNode(T value)
    {
        Value = value;
    }
}

前序遍历

递归版

public void PreorderTraversal(TreeNode<T> root)
{
    if (root == null)
        return;
    Console.WriteLine(root.Value);
    PreorderTraversal(root.Left);
    PreorderTraversal(root.Right);
}

非递归

public void PreorderTraversal(TreeNode<T> root)
{
    Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
    var tempRoot = root;
    while (tempRoot != null || stack.Count > 0)
    {
        if (tempRoot != null)
        {
            Console.WriteLine(tempRoot.Value);
            stack.Push(tempRoot);
            tempRoot = tempRoot.Left;
        }
        else
        {
            var node = stack.Pop();
            tempRoot = node.Right;
        }
    }
}