InorderIterator类的实现

接口的定义:

public interface MyIterator<T> {
	public boolean hasNext();
	public T next();
}

实现接口:

package InorderIterator;

import TraverseTree.TNode;
import TraverseTree.TraverseTree;
import java.util.NoSuchElementException;
import java.util.Stack;

public class InorderIterator<T> implements MyIterator<T> {

	private Stack<TNode<T>> s = null;
	private TNode<T> curr = null;

	private TNode<T> goFarLeft(TNode<T> t) {
		if(t == null)
			return null;
		while(t.left != null) {
			s.push(t);
			t = t.left;
		}
		return t;
	}

	public InorderIterator(TNode<T> root) {
		s = new Stack<TNode<T>>();
		curr = this.goFarLeft(root);
	}

	public T next() {
		if(curr == null)
			throw new NoSuchElementException("no elements remaining!");
		//返回的值
		T value = curr.nodeValue;
		
		if(curr.right != null)
			curr = this.goFarLeft(curr.right);
		else if(!s.isEmpty())
			curr = (TNode<T>)s.pop();
		else
			curr = null;
		
		return value;
	}

	public boolean hasNext() {
		return curr != null;
	}

	public static void main(String[] args) {
		TNode<Character> root = TraverseTree.buildTree(0);
		MyIterator<Character> it = new InorderIterator<Character>(root);
		while(it.hasNext()) {
			char c = it.next();
			System.out.println(c);
		}
	}

}