中序遍历

中序遍历(左头右)：F -> D -> H -> G -> I -> B -> E -> A -> C

中序遍历（递归） #

public static void in(Node head) {
  if (head == null) return;

  in(head.left);
  System.out.print(head.value + " ");
  in(head.right);
}

中序遍历（非递归 单栈） #

public static void in(Node head) {
  System.out.print("in-order: ");
  if (head != null) {
    Stack<Node> stack = new Stack<Node>();
    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;
      }
    }
  }
  System.out.println();
}