1、二叉树

一个树最多只有左孩子和右孩子的树，叫做二叉树。其结构为：

  public static class Node {
    public Node left;
    public Node right;
    public int value;

    public Node(int data) {
      value = data;
    }
  }

2、先序，中序，后序递归版本

对于二叉树先序，中序，后序遍历，其递归版本都非常相似，唯一区别就是打印的时机。因此根据打印时机分为先序，中序，后序。

先序遍历

  /// 先序遍历，递归版本
  public static void preOrder1(Node head) {
    if (head == null) {
      return;
    }
    System.out.print(head.value + " ");
    preOrder1(head.left);
    preOrder1(head.right);
  }

中序遍历

  /// 中序遍历，递归版本
  public static void inOrder1(Node head) {
    if (head == null) {
      return;
    }
    inOrder1(head.left);
    System.out.print(head.value + " ");
    inOrder1(head.right);
  }

后序遍历

  /// 后序遍历，递归版本
  public static void posOrder1(Node head) {
    if (head == null) {
      return;
    }
    posOrder1(head.left);
    posOrder1(head.right);
    System.out.print(head.value + " ");
  }

3、先序，中序，后序非递归版本

先序遍历

为了实现非递归，我们需要通过栈来辅助，模拟栈的操作。由于先序遍历的顺序是，先中，再左，再右。那么我们对于每一个节点，先打印其节点，然后压入右子树，再压入左子树，就可以实现先中，再左，再右的顺序。

代码实现：

  /// 先序遍历，非递归
  public static void preOrder2(Node head) {
    Stack<Node> stack = new Stack<Node>();
    if(head != null) {
      // 先打印，再入栈
      stack.push(head);
      while(!stack.isEmpty()) {
        // 模拟系统栈操作
        head = stack.pop();
        System.out.print(head.value + " ");
        // 由于是先遍历左子树，因此入栈顺序是先右，再左
        if (head.right != null) {
          stack.push(head.right);
        }
        if (head.left != null) {
          stack.push(head.left);
        }
      }
    }
  }

中序遍历

同样地，我们需要一个栈辅助。由于中序遍历的打印顺序是先左，再中，再右。因此，我们需要先将一个节点的左子树全部入栈后，取出栈顶节点打印后，再将该节点的右子树入栈。

代码实现:

  /// 中序遍历，非递归
  public static void inOrder2(Node head) {
    Stack<Node> stack = new Stack<Node>();
    if (head != null) {
      while(!stack.isEmpty() || head != null) {
        // 先压左子树
        if (head != null) {
          stack.push(head);
          head = head.left;
        }else {
          // 左子树压完后，就打印栈顶元素，然后压右子树
          head = stack.pop();
          System.out.print(head.value + " ");
          head = head.right;
        }
      }
    }
  }

后序遍历

后序遍历的非递归版本的有许多实现方法，有标记该树的入栈次数等方法。但最简单的方法是通过两个栈的方式，我们知道后序遍历的顺序是 左右中，那么我们先实现一个改进的先序遍历，其顺序是 中右左，然后将打印操作改为入栈操作。待以中右左的打印的节点全部入栈后，一一出栈，就实现了 左右中的后序遍历了。

代码如下：

  /// 后序遍历，非递归
  public static void posOrder2(Node head) {
    if (head != null) {
      // 由于后续遍历的顺序是 左右打印，因此构造一个先序遍历（打印右左）
      // 的非递归版，然后通过栈2逆序输出即可得到 左右打印 的顺序
      Stack<Node> s1 = new Stack<Node>();
      Stack<Node> s2 = new Stack<Node>();
      s1.push(head);
      while (!s1.isEmpty()) {
        head = s1.pop();
        s2.push(head);
        if (head.left != null) {
          s1.push(head.left);
        }
        if (head.right != null) {
          s1.push(head.right);
        }
      }
      while(!s2.isEmpty()) {
        System.out.print(s2.pop().value + " ");
      }
    }
  }

4、层级遍历

层级遍历就是从根节点开始逐层打印。因此，每打印一个节点，我们都要对其左孩子，右孩子进行打印，那么我们可以通过队实现层次遍历

代码如下:

  /// 层级遍历
  public static void levelOrder(Node head) {
    if (head == null) {
      return;
    }
    Queue<Node> queue = new LinkedList<Node>();
    queue.offer(head);
    System.out.print(head.value + " ");
    while(!queue.isEmpty()) {
      head = queue.poll();
      if (head.left != null) {
        System.out.print(head.left.value + " ");
        queue.offer(head.left);
      }
      if (head.right != null) {
        System.out.print(head.right.value + " ");
        queue.offer(head.right);
      }
    }
  }