二叉树是一种非常重要的数据结构，基于二叉树可以演变出很多其它的数据结构。
二叉树遍历分为：前序遍历、中序遍历、后序遍历、层序遍历
二叉树特殊结构决定了天然适合递归遍历，但非递归实现同样很重要，必须熟练掌握。
四种遍历的思想：

• 前序遍历：根结点 —> 左子树 —> 右子树
• 中序遍历：左子树 —> 根结点 —> 右子树
• 后序遍历：左子树 —> 右子树 —> 根结点
• 层次遍历：只需按层次遍历即可

**（先、中、后）序遍历**通常使用**栈**（stack）或**递归**来实现
**层序遍历**通常使用**队列**（queue）来实现

二叉树示例图

节点的代码定义

public class Node
{
    public int value;
    public Node left;
    public Node right;
    public Node(int value, Node left = null, Node right = null)
    {
        this.value = value;
        this.left = left;
        this.right = right;
    }
    public override string ToString()
    {
        return value + " ";
    }
}

二叉树创建

Node root = new Node(1);

Node child_2 = new Node(2);
Node child_3 = new Node(3);
Node child_4 = new Node(4);
Node child_5 = new Node(5);
Node child_6 = new Node(6);
Node child_7 = new Node(7);
Node child_8 = new Node(8);

root.left = child_2;
root.right = child_3;

child_2.left = child_4;
child_2.right = child_5;

child_3.right = child_6;

child_5.left = child_7;
child_5.right = child_8;

return root;

一、先序遍历

先访问根节点，再访问左子树，最后访问右子树

1、递归实现

// 先序遍历 - 递归实现        
public static void PreOrderRecursion(Node node)
{
    if (node != null)
    {
        Console.Write(node.value + ", ");
        PreOrderRecursion(node.left);
        PreOrderRecursion(node.right);
    }
}

2、非递归实现
先访问当前节点，再访问左子树、再访问右子树，代码的核心就是使用栈来存储遍历的节点，我们在遍历左子树结束后还能回到父节点。

步骤如下：

1. 打印当前节点，并把当前节点入栈，当前节点=左节点

2. 判断当前节点是否为空

   1. 为空，取出栈顶节点，将当前节点=右节点

   2. 不为空，继续重复 1 直到栈为空

      // 先序遍历 - 非递归实现
      public static void Preorder(Node root)
      {
      Stack<Node> stack = new Stack<Node>();
      Node node;
      
      while (root != null || stack.Count > 0)
      {
        // 遍历至末端左子树
        while (root != null)
        {
            Console.Write(root);
            stack.Push(root);
            root = root.left;
        }
      
        node = stack.Pop();
        root = node.right;
      }
      }
      

实现方式二：

• 初始化栈 stack，初始化结果列表 result
• 根节点入栈
• while(栈不为空)
  • 栈顶元素出栈
  • result添加栈顶元素
  • 如果栈顶元素的右子树节点不为空，将右子树节点入栈
  • 如果栈顶元素的左子树节点不为空，将左子树节点入栈

• result结果列表中存储着先序遍历结果

  public static void PreOrder2(Node root)
  {
    Stack<Node> stack = new Stack<Node>();
    stack.Push(root);
    Node node = null;
  
    while (stack.Count > 0)
    {
        node = stack.Pop();
  
        Console.Write(node);
  
        if (node.right != null)
        {
            stack.Push(node.right);
        }
        if (node.left != null)
        {
            stack.Push(node.left);
        }
    }
  }
  

二、中序遍历

先访问左子树，再访问根节点，最后访问右子树
1.1 递归实现

// 中序遍历 - 递归实现
public static void LDRRecursion(Node node)
{
    if (node != null)
    {
        LDRRecursion(node.left);
        Console.Write(node);
        LDRRecursion(node.right);
    }
}

1.2 非递归实现

// 中序遍历 - 非递归实现
public static void LDR(Node root)
{
    Stack<Node> stack = new Stack<Node>();
    Node node;

    while (root != null || stack.Count > 0)
    {
        // 遍历至末端左子树
        while (root != null)
        {
            stack.Push(root);
            root = root.left;
        }

        node = stack.Pop();
        Console.Write(node);
        root = node.right;
    }
}

三、后序遍历

先访问左子树，再访问右子树、最后访问根节点值。
后序遍历不同于前面两种遍历，后序遍历是在完成左子树、右子树遍历之后才进行根节点输出，因此后序遍历中，根节点输出需要判断其左右子树是否都遍历完了。所以我们需要设置一个变量来标记是否遍历完右子树。

1.1 递归实现

// 后序遍历二叉树 - 递归实现
public static void PostorderRecursion(Node node)
{
    if (node != null)
    {
        PostorderRecursion(node.left);
        PostorderRecursion(node.right);
        Console.Write(node);
    }
}

1.2 非递归实现
后序遍历的非递归实现和前序遍历、中序遍历的非递归实现有点不同。需要思考一下。

// 后序遍历 - 非递归实现
public static void Postorder(Node root)
{
    Stack<Node> stack = new Stack<Node>();
    Node prev = null;

    while (root != null || stack.Count > 0)
    {
        while (root != null)
        {
            stack.Push(root);
            root = root.left;
        }

        root = stack.Pop();

        // 如果没有右子树或右子树已经遍历过了
        if (root.right == null || root.right == prev)
        {
            Console.Write(root); // 输出
            prev = root;
            root = null;
        }
        else
        {
            stack.Push(root);
            root = root.right;
        }
    }
}

方式二：

• 初始化栈stack，结果列表res
• 根节点入栈
• while(栈不为空)
  • 栈顶元素出栈
  • res添加栈顶元素
  • 如果栈顶元素的左子树节点不为空，将左子树节点入栈
  • 如果栈顶元素的右子树节点不为空，将右子树节点入栈

• res 反序输出

  public static void Test2(Node root)
  {
    if (root == null) return;
  
    Stack<Node> stack = new Stack<Node>();
    List<int> res = new List<int>();
    Node node = null;
  
    stack.Push(root);
  
    while(stack.Count > 0)
    {
        node = stack.Pop();
  
        Console.Write(node);
  
        if(node.left != null)
        {
            stack.Push(node.left);
        }
        if(node.right != null)
        {
            stack.Push(node.right);
        }
    }
  }
  

二、层序遍历

从上往下，从左往右（从左往右）访问每一层的节点，当前层节点访问完开始下一层，直到所有节点全部访问完。

非递归实现

// 层序遍历 - 非递归实现
public static void Levelorder(Node root)
{
    Queue<Node> queue = new Queue<Node>();
    queue.Enqueue(root);

    while (queue.Count > 0)
    {
        root = queue.Dequeue();

        Console.Write(root);

        if (root.left != null)
        {
            queue.Enqueue(root.left);
        }
        if (root.right != null)
        {
            queue.Enqueue(root.right);
        }
    }
}

任何递归形式的算法都能够通过栈、队列等数据结构转变成非递归形式

五、时间复杂度、空间复杂度

非递归：
（先、中、后）序遍历需要辅助栈，且每一个节点都会进出栈，**时间复杂度O(n)**、**空间复杂度O(n)**
层序遍历通过辅助队列，且每一个节点都会入队、出队，**时间复杂度O(n)**、**空间复杂度O(n)**
递归版：
系统底层对于递归调用会创建栈来保存调用顺序，**时间复杂度O(n)**、**空间复杂度O(n)**

莫里斯（Morris）算法 对于一般的遍历算法，我们都是利用栈来存储之后需要再次访问的节点。最差情况下，我们需要存储整个二叉树节点。所以空间复杂度为O(n)。而Morris遍历则是将空间复杂度降到了O(1)级别。Morris遍历用到了“线索二叉树”的概念，其实就是利用了叶子节点的左右空指针来存储某种遍历前驱节点或者后继节点。因此没有使用额外的空间。

参考

二叉树文章 https://blog.csdn.net/u010414589/article/details/115415388