Re: PreOrder Tree Traversal

Jeff Higgins wrote:


public boolean hasNext() {

Here is Michael Abrash's algorithm, adapted to Java. Anywhere I have the "vistNode()" call, you should return "true." Where I return, you should return "false." This is an in-order traversal, it shouldn't be hard to adapt to pre-order.

private void abrashInOrder() {
// Micheal Abrash, Zen of graphics programming.
if (this.tree == null) {
return;
}

Stack<BinaryTreeNode> nodeStack = new Stack<BinaryTreeNode>();
BinaryTreeNode curr = this.tree;

while (true) {
while (curr.left != null) {
nodeStack.push(curr);
curr = curr.left;
}
while (true) {
visitNode(curr);
if (curr.right != null) {
curr = curr.right;
break;
}
if (!nodeStack.isEmpty()) {
curr = nodeStack.pop();
} else {
return;
}
}
}
}

Here is the Morris algorithm. It uses no stack, but does modify the tree as it traverses it. It therefore probably is not well suited to multi-tasking and concurrent use, but it will traverse any tree with no additional memory requirement, making it highly deterministic, and also very pithy on low-memory systems.

private void morrisInOrder() {
// J. M. Morris, "Traversing binary trees simply and cheaply"
// Information Processing Letters, December 1979
if (this.tree == null) {
return;
}
BinaryTreeNode p = tree;
while (p != null) {
if (p.left == null) {
visitNode(p);
p = p.right;
} else {
BinaryTreeNode pre = p.left;
while (pre.right != null && pre.right != p) {
pre = pre.right;
}
if (pre.right == null) {
pre.right = p;
p = p.left;
} else {
pre.right = null;
visitNode(p);
p = p.right;
}
}
}
}
.

Relevant Pages

  • Re: PreOrder Tree Traversal
    ... You might try to simplify your algorithm here. ... The structure I am envisioning is a binary tree, ... BinaryTreeNode curr = this.tree; ...
    (comp.lang.java.help)
  • Re: PreOrder Tree Traversal
    ... Namely, looking at Sedgewick's algorithm, I see: ... BinaryTreeNode current; ... It's simpler because it uses a simpler tree node structure too, but I think the algorithm is simpler, period. ... private void insertNode{ ...
    (comp.lang.java.help)