浏览 3138 次
锁定老帖子 主题:二叉树遍历(递归/非递归)
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2009-06-26
最后修改:2009-06-26
//Node public class Node { private Node left; private Node right; private Object value; public Node(Node left, Node right, Object value) { super(); this.left = left; this.right = right; this.value = value; } public Node left() { return left; } public Node right() { return right; } public Object value() { return value; } } //遍历访问操作接口 public interface Visitor { public void visit(Node obj); } //实现 public class BinaryTreeScan { public void firstRootScan(Node node, Visitor visitor) { if (node == null) return; visitor.visit(node); this.firstRootScan(node.left(), visitor); this.firstRootScan(node.right(), visitor); } public void midRootScan(Node node, Visitor visitor) { if (node == null) return ; this.midRootScan(node.left(), visitor); visitor.visit(node); this.midRootScan(node.right(), visitor); } public void lastRootScan(Node node, Visitor visitor) { if (node == null) return ; this.lastRootScan(node.left(), visitor); this.lastRootScan(node.right(), visitor); visitor.visit(node); } public void firstRootScanNonRecursion(Node node, Visitor visitor) { if (node == null) return ; Stack stack = new Stack(); stack.push(node); while(!stack.empty()) { Node n = (Node) stack.pop(); visitor.visit(n); if (n.right() != null) stack.push(n.right()); if (n.left() != null) stack.push(n.left()); } } } //tester public class Main { public static void main(String[] args) { Node b = new Node(new Node(null,null,"d"),new Node(null,null,"e"),"b"); Node a = new Node(b, new Node(new Node(null,null,"f"),null,"c"),"a"); BinaryTreeScan binaryTreeScan = new BinaryTreeScan(); StringBuilder sb = new StringBuilder(); binaryTreeScan.firstRootScanNonRecursion(a,new VisitorStringBuffer(sb)); System.out.println(sb.toString()); } } class VisitorStringBuffer implements Visitor { private final StringBuilder sb; VisitorStringBuffer(StringBuilder sb) { this.sb = sb; } public void visit(Node obj) { sb.append(obj.value()); } } 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |