import java.util.*;
/** Binary Tree (not balanced) by Douglas A. Bauman
** also includes Iterator operation on the tree (inorder)
**/
public class NodeT<T> implements Iterable<T>
{
Integer data;
NodeT left;
NodeT right;
NodeT parent;
/* iterator and iterable contracts */
public Iterator<T> iterator() {
NodeTIterator result = new NodeTIterator(this);
return result;
}
private class NodeTIterator implements Iterator<T> {
NodeT cur;
public NodeTIterator(NodeT n) {
this.cur = n.getLeftMost();
}
/* Returns true if the iteration has more elements. */
public boolean hasNext() {
return cur != null;
}
/* Returns the next element in the iteration.*/
public T next() {
T r = null;
if (cur != null) {
r = (T)cur;
cur = ((NodeT)cur).getNext();
}
return r;
}
/* Removes from the underlying collection the last element returned by the iterator (optional operation). */
public void remove() {throw new UnsupportedOperationException("remove not implemented for NodeTIterator");}
}
/* constructor */
public NodeT(Integer data, NodeT parent) {
this.data = data;
this.parent = parent;
}
public NodeT getLeftMost() {
NodeT n = this;
while (n.left != null) {
n = n.left;
}
return n;
}
public NodeT getNext() {
if (right != null) {
return right.getLeftMost();
} else {
NodeT n = this;
while (n.parent != null && n == n.parent.right) {
n = n.parent;
}
return n.parent;
}
}
/* recursively insert the data as a new node at the appropriate place using inorder placement */
public NodeT insert(NodeT n, Integer data, int level, NodeT parent) {
if (n == null) {
// create new node
n = (NodeT) new NodeT(data, parent);
} else if (((Integer)data).intValue() > ((Integer)n.data).intValue()) {
n.right = insert(n.right, data, level+1, n);
} else {
n.left = insert(n.left, data, level+1, n);
}
return n;
}
/** inorder find data in the tree by iterating, will be O(N) because iteration is in sort order, so not a good algorithm */
public NodeT find(Integer data) {
NodeT cur = getLeftMost();
while (cur != null) {
System.out.println("searching :"+cur.data);
if (cur.data.intValue() == data.intValue()) return cur;
cur = cur.getNext();
}
return null;
}
/* recursively find the data: should be O(logN) if this were a balanced tree (but it's not), but if it were, then this would be the better search */
public NodeT findrec(Integer data, int level) {
System.out.println("finding...:"+data+", this.data:"+this.data+" level:"+level);
if (right!=null && data.intValue() > this.data.intValue()) {
System.out.println("searching right:"+right.data);
return right.findrec(data, level+1);
} else if (data.intValue() == this.data.intValue()) {
System.out.println("eq");
return this;
} else if (left!=null && data.intValue() < this.data.intValue()) {
System.out.println("searching left:"+left.data);
return left.findrec(data, level+1);
}
return null;
}
public void dumpnode(String tag, int level) {
System.out.println("data: "+data+
" "+tag+", parent: "+(parent==null?"null":""+parent.data)+
", left: "+(left==null?"null":""+left.data)+
", right: "+(right==null?"null":""+right.data)
//", level:" +level
);
}
/** inorder dump of the tree, so the values come out sorted **/
public void dumptree(String tag, int level) {
NodeT cur = getLeftMost();
while (cur != null) {
System.out.print(" " + cur.data);
cur = cur.getNext();
}
System.out.println("");
}
/** inorder recursive dump of the tree, so the values come out sorted **/
public void dumptreerec(String tag, int level) {
if (left != null) left.dumptreerec("left", level+1);
dumpnode(tag, level);
if (right != null) right.dumptreerec("right", level+1);
}
public void dump(String tag) {
System.out.println("In-Order Dump ("+tag+")");
dumptree("root", 1);
}
public static void main(String[] args) {
int array[] = { 3, 9, 1, 4, 8, 2, 5, 7, 0, 6 };
// this array will generate: __3__
//data: 0 (left) / \
//data: 1 (left) 1 9
//data: 2 (right) /\ /
//data: 3 (root) 0 2 4
//data: 4 (left) \
//data: 5 (left) 8
//data: 6 (left) /
//data: 7 (right) 5
//data: 8 (right) \
//data: 9 (right) 7
// /
// 6
int i;
NodeT base = new NodeT(array[0], null);
String buffer = "after added node " + array[0];
base.dump(buffer);
for (i = 1; i < array.length; i++) {
buffer = "after added node " + array[i];
base = base.insert(base, array[i], 1, null);
base.dump(buffer);
}
System.out.println("\nrecursive dump:");
base.dumptreerec("root", 1);
System.out.println("\nrecursively find 9:");
NodeT n = base.findrec(9, 1);
if (n==null) System.out.println("...can't find 9");
else n.dumpnode("found", 1);
System.out.println("\n iteratively find 9:");
n = base.find(9);
if (n==null) System.out.println("...can't find 9");
else n.dumpnode("found", 1);
System.out.println("\niterate.....");
for(Object k : base) {
System.out.println("next k:"+((NodeT)k).data);
}
}
//output will look like this:
// In-Order Dump (after added node 3)
// 3
// In-Order Dump (after added node 9)
// 3 9
// In-Order Dump (after added node 1)
// 1 3 9
// In-Order Dump (after added node 4)
// 1 3 4 9
// In-Order Dump (after added node 8)
// 1 3 4 8 9
// In-Order Dump (after added node 2)
// 1 2 3 4 8 9
// In-Order Dump (after added node 5)
// 1 2 3 4 5 8 9
// In-Order Dump (after added node 7)
// 1 2 3 4 5 7 8 9
// In-Order Dump (after added node 0)
// 0 1 2 3 4 5 7 8 9
// In-Order Dump (after added node 6)
// 0 1 2 3 4 5 6 7 8 9
//
// recursive dump:
// data: 0 left, parent: 1, left: null, right: null
// data: 1 left, parent: 3, left: 0, right: 2
// data: 2 right, parent: 1, left: null, right: null
// data: 3 root, parent: null, left: 1, right: 9
// data: 4 left, parent: 9, left: null, right: 8
// data: 5 left, parent: 8, left: null, right: 7
// data: 6 left, parent: 7, left: null, right: null
// data: 7 right, parent: 5, left: 6, right: null
// data: 8 right, parent: 4, left: 5, right: null
// data: 9 right, parent: 3, left: 4, right: null
//
// recursively find 9:
// finding...:9, this.data:3 level:1
// searching right:9
// finding...:9, this.data:9 level:2
// eq
// data: 9 found, parent: 3, left: 4, right: null
//
// iteratively find 9:
// searching :0
// searching :1
// searching :2
// searching :3
// searching :4
// searching :5
// searching :6
// searching :7
// searching :8
// searching :9
// data: 9 found, parent: 3, left: 4, right: null
//
// iterate.....
// next k:0
// next k:1
// next k:2
// next k:3
// next k:4
// next k:5
// next k:6
// next k:7
// next k:8
// next k:9
}
Another idea:
class Node {
int data;
Node left;
Node right;
Node(int data)
{
this.data = data;
left = right = null;
}
}
class InorderIterator {
private Stack<Node> traversal;
InorderIterator(Node root)
{
traversal = new Stack<Node>();
moveLeft(root);
}
private void moveLeft(Node current)
{
while (current != null) {
traversal.push(current);
current = current.left;
}
}
public boolean hasNext()
{
return !traversal.isEmpty();
}
public Node next()
{
if (!hasNext())
throw new NoSuchElementException();
Node current = traversal.pop();
if (current.right != null)
moveLeft(current.right);
return current;
}
}
class Test {
public static void main(String args[])
{
Node root = new Node(8);
root.right = new Node(9);
root.left = new Node(3);
root.left.left = new Node(2);
root.left.right = new Node(4);
root.left.right.right = new Node(5);
InorderIterator itr = new InorderIterator(root);
try {
System.out.print(itr.next().data + " ");
System.out.print(itr.hasNext() + " ");
System.out.print(itr.next().data + " ");
System.out.print(itr.next().data + " ");
System.out.print(itr.next().data + " ");
System.out.print(itr.hasNext() + " ");
System.out.print(itr.next().data + " ");
System.out.print(itr.next().data + " ");
System.out.print(itr.hasNext() + " ");
}
catch (NoSuchElementException e) {
System.out.print("No such element Exists");
}
}
}
