树的非递归先序遍历

对于树的遍历操作，通常使用递归的方式写起来比较简单。但是偶尔也可以尝试一下非递归的写法。

 

public void preOrder(Node t) {
    if (t == null)
        return;
		
    Stack<Node> stack = new Stack<Node>();
    Stack<Node> remain = new Stack<Node>();
	
    while (true) {
        System.out.print((t.value + " "));
        stack.push(t);
	
        if (t.left != null) {
            if (t.right != null) {
                remain.push(t.right);
            }
            t = t.left;
        } else if (t.right != null) {
            t = t.right;
        } else if (!remain.isEmpty()) {
            while (stack.peek().right != remain.peek()) {
                stack.pop();
            }
            t = remain.pop();
        } else {
            break;
        }
    }
}