Mercurial > hg > Members > shoshi > TreeCMS > TreeCMSPrototype1
view src/treecms/proto/util/PreOrderTreeWalker.java @ 27:45881237e777
commit
author | ShoshiTAMAKI |
---|---|
date | Sun, 07 Nov 2010 14:07:03 +0900 |
parents | src/treecms/proto/test/PreOrderTreeWalkerRecursive.java@9b91329e8a04 |
children |
line wrap: on
line source
package treecms.proto.util; import java.util.Iterator; import java.util.LinkedList; import treecms.proto.api.Node; public class PreOrderTreeWalker implements Iterable<Node> { private Node m_root; public PreOrderTreeWalker(Node _root) { m_root = _root; } @Override public Iterator<Node> iterator() { return new PreOrderRecursiveIterator(m_root); } class PreOrderRecursiveIterator implements Iterator<Node> { private LinkedList<Node> nextList; public PreOrderRecursiveIterator(Node _root) { nextList = new LinkedList<Node>(); getChildren(_root, nextList); } void getChildren(Node node, LinkedList<Node>list) { list.add(node); for(Node child : node.getChildren()){ getChildren(child,list); } } @Override public boolean hasNext() { return !nextList.isEmpty(); } @Override public Node next() { return nextList.poll(); } @Override public void remove() { throw new UnsupportedOperationException("cant remove from itrerator"); } } public LinkedList<Node> findPath(Node root, Node node) { LinkedList<Node> list = new LinkedList<Node>(); list.addFirst(root); findPath(root,node,list); return list; } private boolean findPath(Node root, Node node, LinkedList<Node> list) { if (root==node) return true; for(Node child : node.getChildren()){ if (findPath(child,node,list)) { list.addFirst(child); return true; } } return false; // backtrack } }