关键就是要用一个栈来保存遍历路径。主要涉及类如下：
class TreeNode 这个类用来声明树的结点，其中有左子树、右子树和自身的内容。
class MyTree 这个类用来声明一棵树，传入根结点。这里设计的比较简单
class TreeEum 这个类是树的迭代器，通过MyTree类的方法获取，这里主要就是设计它了。代码如下：
//TreeNode类，使用了泛型，由于比较简单，青年人网提示不作解释
class TreeNode<E>
{
E node;
private TreeNode<String> left;
private TreeNode<String> right;
public TreeNode(E e)
{
this(e,null,null);
}
public TreeNode(E e,TreeNode<String> left,TreeNode<String> right)
{
this.node=e;
this.left=left;
this.right=right;
}
public TreeNode<String> left()
{
return left;
}
public TreeNode<String> right()
{
return right;
}
}
//MyTree类，没什么功能，传入根结点构造，getEnumerator()方法获取迭代器。
class MyTree
{
TreeNode<String> root;
public MyTree(TreeNode<String> root)
{
this.root=root;
}
public TreeEnum getEnumerator()
{
return new TreeEnum(root);
}
}
//这个类为迭代器，有详细解释，相信各位能看懂。在栈中用了两次泛型。
import java.util.Stack;
public class TreeEnum
{
private TreeNode<String> root;
private Stack<TreeNode<String>> store;/*保存遍历左子树但未遍历右子树的结点*/
private TreeNode<String> next;
public TreeEnum(TreeNode<String> root)
{
this.root=root;
store=new Stack<TreeNode<String>>();
next=root;
}
public TreeNode<String> next()
{
TreeNode<String> current=next;
if(next!=null)
{
/*如果当前结点的左子树不为空,则遍历左子树,并标记当前结点未遍历右子树*/
if(next.left()!=null)
{
store.push(next);
next=next.left();
}
//如果当前结点的左子树为空,则遍历右子树
else if(next.right()!=null)
{
next=next.right();
}
/*如果当前结点为叶子,则找未遍历右子树的结点并且遍历它的右子树*/
else{
if(!store.empty())/*判断是否还有结点的右子树未遍历*/
{
TreeNode<String> tmp=store.pop();
/*如果有未遍历右子树的结点,但它的右子树为空,且还有结点的右子树未遍历,*/
/*则一直往上取,直到取到未遍历右子树且右子树不为空的结点,遍历它的右子树.*/
while((tmp.right()==null)&&!store.empty())
{
tmp=store.pop();
}
next=tmp.right();
}
else
{
/*如果没有哪个结点右子树未遍历,则表示没有下一个结点了,设置next为null*/
next=null;
}
}
}
return current;
}
public boolean hasMoreElement()
{
return next!=null;
}
}
下面写个测试类，不作解释，相信大家看得懂
public class TreeReader{
public static void main(String[] args)
{
TreeNode<String> n1=new TreeNode<String>("n1");
TreeNode<String> n2=new TreeNode<String>("n2");
TreeNode<String> n3=new TreeNode<String>("n3");
TreeNode<String> n4=new TreeNode<String>("n4");
TreeNode<String> n5=new TreeNode<String>("n5");
TreeNode<String> n6=new TreeNode<String>("n6",null,n1);
TreeNode<String> n7=new TreeNode<String>("n7",n2,null);
TreeNode<String> n8=new TreeNode<String>("n8",n7,null);
TreeNode<String> n9=new TreeNode<String>("n9",null,n5);
TreeNode<String> n10=new TreeNode<String>("n10",n4,n9);
TreeNode<String> n11=new TreeNode<String>("n11",n6,n8);
TreeNode<String> n12=new TreeNode<String>("n12",n3,n10);
TreeNode<String> root=new TreeNode<String>("root",n11,n12);
MyTree tree=new MyTree(root);
TreeEnum eum=tree.getEnumerator();
while(eum.hasMoreElement())
{
System.out.print(eum.next().node+"--");
}
System.out.println("end");
}
}
由于急着实现迭代器，所以没有去实现其他功能，迭代器类写的也匆忙，还有很多可改进的地方，青年人网希望各位朋友可以提出意见和建议。
责任编辑：虫虫
