二叉树的常用遍历方法

二叉树常用的遍历方法包括：

1. 前序遍历
2. 中序遍历
3. 后序遍历
4. 层次遍历

而前三种遍历的具体实现上，又有常见的两种实现方式：

1. 递归遍历
2. 非递归遍历

所以综合来说，常用的二叉树遍历方法包括：

1. 递归前序遍历
2. 递归中序遍历
3. 递归后序遍历
4. 非递归前序遍历
5. 非递归中序遍历
6. 非递归后序遍历
7. 层次遍历

下面，使用java代码实现，整理一下每种遍历方法。

一个简单的二叉树

public class BinaryTree {
  public BinaryTree left;
  public BinaryTree right;
  private int data;

  public void doSomething() {
    // ...
  }

  // 各种遍历方法...
}

递归前序遍历

public static void preOrder(BinaryTree tree) {
 if (tree == null) {
   return;
 }
 tree.doSomething();
 preOrder(tree.left);
 preOrder(tree.right);
}

递归中序遍历

public static void inOrder(BinaryTree tree) {
 if (tree == null) {
   return;
 }
 inOrder(tree.left);
 tree.doSomething();
 inOrder(tree.right);
}

递归后序遍历

public static void postOrder(BinaryTree tree) {
 if (tree == null) {
   return;
 }
 postOrder(tree.left);
 postOrder(tree.right);
 tree.doSomething();
}

一个简单的队列

public class Queue<T> {
  private static class Node {
    T data;
    Node next;

    Node(T t) {
      data = t;
    }
  }
  
  private Node mFirst = new Node();
  private Node mEnd = mFirst;

  public void enqueue(T data) {
    Node node = new Node(data);
    mEnd.next = node;
    mEnd = node;
  }

  public T dequeue() {
    if (mFirst == mEnd) {
      return null;
    }
    Node node = mFirst;
    mFirst = mFirst.next;
    return node.data;  
  }
}

一个简单的栈

public class Stack<T> {
  private static class Node {
    BinaryTree data;
    Node pre;
    Node next;

    Node(T t) {
      data = t;
    }
  }

  private Node mTop = new Node();
  private Node mBottom = mTop;

  public void push(T data) {
    Node node = new Node(data);
    mTop.next = node;
    node.pre = mTop.pre;
    mTop = node;
  }

  public T pop() {
    if (empty()) {
      return null;
    }
    mTop = mTop.pre;
    return mTop.next.data;
  }

  public boolean empty() {
    return mTop == mBottom;
  }
}

层次遍历

public static levelOrder(BinaryTree tree) {
  Queue<BinaryTree> queue = new Queue<BinaryTree>();
  if (tree != null) {
    queue.enqueue(tree); 
  }
  BinaryTree node = queue.dequeue();
  while (node != null) {
    node.doSomething();
    if (node.left != null) {
      queue.enqueue(node.left);
    }
    if (node.right != null) {
      queue.enqueue(node.right);
    }
    node = queue.dequeue();
  }
}

非递归前序遍历

public static preOrder(BinaryTree tree) {
  Stack stack<BinaryTree> = new Stack<BinaryTree>();
  BinaryTree node = tree;
  while (node != null || !stack.empty()) {
    while (node != null) {
      stack.push(node);
      node.doSomething();
      node = node.left;
    }
    if (!stack.empty()) {
      node = stack.pop();
      node = node.right;
    }
  }
}

非递归中序遍历

public static inOrder(BinaryTree tree) {
  Stack stack<BinaryTree> = new Stack<BinaryTree>();
  BinaryTree node = tree;
  while (node != null || !stack.empty()) {
    while (node != null) {
      stack.push(node);
      node = node.left;
    }
    if (!stack.empty()) {
      node = stack.pop();
      node.doSomething();
      node = node.right;
    }
  }
}

非递归后序遍历

private static class PostTreeNode {
  BinaryTree tree;
  boolean firstVisit;

  PostTreeNode(BinaryTree biTree) {
    tree = biTree;
  }
}

public static postOrder(BinaryTree tree) {
  Stack stack<PostTreeNode> = new Stack<PostTreeNode>();
  BinaryTree node = tree;
  while (node != null || stack != null) {
    while (node != null) {
      PostTreeNode treeNode = new PostTreeNode(node);
      treeNode.firstVisit = true;
      stack.push(treeNode);
      node = node.left;
    }
    if (stack != null) {
      PostTreeNode treeNode = stack.pop();
      if (treeNode.firstVisit) {
        treeNode.firstVisit = false;
        stack.push(treeNode);
        node = treeNode.tree.right;
      } else {
        treeNode.tree.doSomething();
        node = null;
      }
    }
  }
}