PreOrder Tree Traversal
Need help with my Tree.PreOrderIterator,
stack is stuck;
prints ABC,
should print ABCDEFG ,
what am I doing wrong?
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
public class Launcher {
public static class Node {
String data;
public Node(String data) {
this.data = data; }
@Override
public String toString() {
return data; }
}
public static class Edge {
Node source;
Node target;
public Edge(Node source, Node target) {
this.source = source;
this.target = target; }
}
public static class EdgeContainer {
Edge root; Edge left; Edge right;
public EdgeContainer() {}
public EdgeContainer(Edge root, Edge left, Edge right) {
this.root = root;
this.left = left;
this.right = right;
}
}
public static class Tree {
private final Node root;
private final Map<Node, EdgeContainer> nodeMap;
public Tree() {
nodeMap = new HashMap<Node, EdgeContainer>();
root = new Node("root");
nodeMap.put(root, new EdgeContainer()); }
public Node getRoot() {
return root; }
EdgeContainer getEdges(Node node) {
return nodeMap.get(node); }
public void addNode(Node node, EdgeContainer edges) {
nodeMap.put(node, edges); }
Iterator<Node> getPreOrderIterator(Node node) {
return new PreOrderIterator(node); }
private class PreOrderIterator implements Iterator<Node> {
Deque<Node> stack = new ArrayDeque<Node>();
boolean check = false;
public PreOrderIterator(Node target) {
if (target != null) {
stack.push(target); } }
@Override
public boolean hasNext() {
if (!stack.isEmpty()) {
EdgeContainer edge = nodeMap.get(stack.pop());
if (edge.left != null) {
if (edge.right != null) {
stack.push(edge.right.target); }
stack.push(edge.left.target);
return true; }
else if (edge.right != null) {
stack.push(edge.right.target);
return true; }
} return false; }
@Override
public Node next() {
if (stack.isEmpty())
throw new NoSuchElementException();
return stack.peek(); }
@Override
public void remove() {
throw new UnsupportedOperationException(); }
}
}
public static void main(String[] args) {
Tree tree = new Tree();
Node na = new Node(new String("A"));
Node nb = new Node(new String("B"));
Node nc = new Node(new String("C"));
Node nd = new Node(new String("D"));
Node ne = new Node(new String("E"));
Node nf = new Node(new String("F"));
Node ng = new Node(new String("G"));
/*
root
|
A------F
| |
| G
|
B------D
| |
| E
|
C
*/
EdgeContainer rootEdges =
tree.getEdges(tree.getRoot());
rootEdges.left = new Edge(tree.getRoot(), na);
tree.addNode(na, new EdgeContainer(
new Edge(tree.getRoot(), na),
new Edge(na, nb),
new Edge(na, nf)));
tree.addNode(nb, new EdgeContainer(
new Edge(na, nb),
new Edge(nb, nc),
new Edge(nb, nd)));
tree.addNode(nc, new EdgeContainer(
new Edge(nb, nc),
null,
null));
tree.addNode(nd, new EdgeContainer(
new Edge(nb, nd),
new Edge(nd, ne),
null));
tree.addNode(ne, new EdgeContainer(
new Edge(nd, ne),
null,
null));
tree.addNode(nf, new EdgeContainer(
new Edge(na, nf),
new Edge(nf, ng),
null));
tree.addNode(ng, new EdgeContainer(
new Edge(nf, ng),
null,
null));
Iterator<Node> iterator =
tree.getPreOrderIterator(tree.getRoot());
while(iterator.hasNext()) {
System.out.print(iterator.next().toString()); }
}
}