二叉树的中序遍历

中序遍历

中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。

            R
       /         
      A          B
  /           /     
C      D     E       F

上面这个树的中序遍历顺序是： C A D R E B F

遍历的实现

• 递归实现
• 迭代实现

递归实现

public class  {
    public static Tree init() {
        Tree E = new Tree(null, null, "E");
        Tree F = new Tree(null, null, "F");
        Tree C = new Tree(null, null, "C");
        Tree D = new Tree(null, null, "D");
        Tree A = new Tree(C, D, "A");
        Tree B = new Tree(E, F, "B");
        Tree root = new Tree(A, B, "R");
        return root;
    }
    public static void main(String[] args) {
        Tree root = init();
        traverse(root);
    }
    private static void traverse(Tree root) {
        if(root == null) {
            return;
        }
        traverse(root.getLeft());
        System.out.print(root.getData() + " ");
        traverse(root.getRight());
    }
}

迭代实现

如下图所示：

import java.util.Stack;
public class InTraverse1 {
    public static Tree init() {
        Tree E = new Tree(null, null, "E");
        Tree F = new Tree(null, null, "F");
        Tree C = new Tree(null, null, "C");
        Tree D = new Tree(null, null, "D");
        Tree A = new Tree(C, D, "A");
        Tree B = new Tree(E, F, "B");
        Tree root = new Tree(A, B, "R");
        return root;
    }
    public static void main(String[] args) {
        Tree root = init();
        traverse(root);
    }
    private static void traverse(Tree root) {
        Stack<Tree> stack = new Stack<>();
        while (true) {
            findLeft(root, stack);
            if (stack.isEmpty()) {
                break;
            }
            Tree popTree = stack.pop();
            //访问栈顶的节点，也就是最左的节点
            System.out.print(popTree.getData() + " ");
            //然后循环遍历右子树
            root = popTree.getRight();
        }
    }
    //沿着当前节点，把所有的左节点push到栈中
    private static void findLeft(Tree root, Stack<Tree> stack) {
        while (root != null) {
            stack.push(root);
            root = root.getLeft();
        }
    }
}