`
eriol
  • 浏览: 399418 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

树的非递归先序遍历

阅读更多

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

 

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;
        }
    }
}
 
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics