关键就是要用一个栈来保存遍历路径。主要涉及类如下：
class TreeNode 这个类用来声明树的结点，其中有左子树、右子树和自身的内容。
class MyTree 这个类用来声明一棵树，传入根结点。这里设计的比较简单
class TreeEum 这个类是树的迭代器，通过MyTree类的方法获取，这里主要就是设计它了。代码如下：
//TreeNode类，使用了泛型，由于比较简单，考试.大提示不作解释
class TreeNode
{
E node;
private TreeNode left;
private TreeNode right;
public TreeNode(E e)
{
this(e,null,null);
}
public TreeNode(E e,TreeNode left,TreeNode right)
{
this.node=e;
this.left=left;
this.right=right;
}
public TreeNode left()
{
return left;
}
public TreeNode right()
{
return right;
}
}
//MyTree类，没什么功能，传入根结点构造，getEnumeraTor()方法获取迭代器。
class MyTree
{
TreeNode root;
public MyTree(TreeNode root)
{
this.root=root;
}
public TreeEnum getEnumeraTor()
{
return new TreeEnum(root);
}
}
//这个类为迭代器，有详细解释，相信各位能看懂。在栈中用了两次泛型。
import java.util.Stack;
public class TreeEnum
{
private TreeNode root;
private Stack> sTore;/*保存遍历左子树但未遍历右子树的结点*/
private TreeNode next;
public TreeEnum(TreeNode root)
{
this.root=root;
sTore=new Stack>();
next=root;
}
public TreeNode next()
{
TreeNode 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 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 n1=new TreeNode(“n1”);
TreeNode n2=new TreeNode(“n2”);
TreeNode n3=new TreeNode(“n3”);
TreeNode n4=new TreeNode(“n4”);
TreeNode n5=new TreeNode(“n5”);
TreeNode n6=new TreeNode(“n6”,null,n1);
TreeNode n7=new TreeNode(“n7”,n2,null);
TreeNode n8=new TreeNode(“n8”,n7,null);
TreeNode n9=new TreeNode(“n9”,null,n5);
TreeNode n10=new TreeNode(“n10”,n4,n9);
TreeNode n11=new TreeNode(“n11”,n6,n8);
TreeNode n12=new TreeNode(“n12”,n3,n10);
TreeNode root=new TreeNode(“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”);
}
}
由于急着实现迭代器，所以没有去实现其他功能，迭代器类写的也匆忙，还有很多可改进的地方，考试大希望各位朋友可以提出意见和建议。
一起交流学习请访问：Tore_m_1206686_21115_1_1.html”>http://www.shangxueba.com/sTore_m_1206686_21115_1_1.html
可我，仍在旅行的路上徘徊。等待着每一辆经过的车，让我走到更远的地方。
