二叉树的中序遍历

中序遍历

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

            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();
		}
	}
}