JAVA技巧(java实现二叉树前序遍历迭代器)

JAVA技巧(java实现二叉树前序遍历迭代器)classTreeNode这个类用来声明树的结点，其中有左子树、右子树和自身的内容。

classMyTree这个类用来声明一棵树，传入根结点。这里设计的比拟简洁

classTreeEum这个类是树的迭代器，通过MyTree类的方法猎取，这里主要就是设计它了。代码如下：

//TreeNode类，使用了泛型，由于比拟简洁，考试.大提示不作解释

classTreeNode

{

Enode;

privateTreeNodeleft;

privateTreeNoderight;

publicTreeNode(Ee)

{

this(e,null,null);

}

publicTreeNode(Ee,TreeNodeleft,TreeNoderight)

{

this.node=e;

this.left=left;

this.right=right;

}

publicTreeNodeleft()

{

returnleft;

}

publicTreeNoderight()

{

returnright;

}

}

//MyTree类，没什么功能，传入根结点构造，getEnumerator()方法猎取迭代器。

classMyTree

{

TreeNoderoot;

publicMyTree(TreeNoderoot)

{

this.root=root;

}

publicTreeEnumgetEnumerator()

{

returnnewTreeEnum(root);

}

}

//这个类为迭代器，有具体解释，信任各位能看懂。在栈中用了两次泛型。

importjava.util.Stack;

publicclassTreeEnum

{

privateTreeNoderoot;

privateStack>store;/*保存遍历左子树但未遍历右子树的结点*/

privateTreeNodenext;

publicTreeEnum(TreeNoderoot)

{

this.root=root;

store=newStack>();

next=root;

}

publicTreeNodenext()

{

TreeNodecurrent=next;

if(next!=null)

{

/*假如当前结点的左子树不为空,则遍历左子树,并标记当前结点未遍历右子树*/

if(next.left()!=null)

{

store.push(next);

next=next.left();

}

//假如当前结点的左子树为空,则遍历右子树

elseif(next.right()!=null)

{

next=next.right();

}

/*假如当前结点为叶子,则找未遍历右子树的结点并且遍历它的右子树*/

else{

if(!store.empty())/*推断是否还有结点的右子树未遍历*/

{

TreeNodetmp=store.pop();

/*假如有未遍历右子树的结点,但它的右子树为空,且还有结点的右子树未遍历,*/

/*则始终往上取,直到取到未遍历右子树且右子树不为空的结点,遍历它的右子树.*/

while((tmp.right()==null)

}

next=tmp.right();

}

else

{

/*假如没有哪个结点右子树未遍历,则表示没有下一个结点了,设置next为null*/

next=null;

}

}

}

returncurrent;

}

publicbooleanhasMoreElement()

{

returnnext!=null;

}

}

下面写个测试类，不作解释，信任大家看得懂

publicclassTreeReader{

publicstaticvoidmain(String[]args)

{

TreeNoden1=newTreeNode(“n1“);

TreeNoden2=newTreeNode(“n2“);

TreeNoden3=newTreeNode(“n3“);

TreeNoden4=newTreeNode(“n4“);

TreeNoden5=newTreeNode(“n5“);

TreeNoden6=newTreeNode(“n6“,null,n1);

TreeNoden7=newTreeNode(“n7“,n2,null);

TreeNoden8=newTreeNode(“n8“,n7,null);

TreeNoden9=newTreeNode(“n9“,null,n5);

TreeNoden10=newTreeNode(“n10“,n4,n9);

TreeNoden11=newTreeNode(“n11“,n6,n8);

TreeNoden12=newTreeNode(“n12“,n3,n10);

TreeNoderoot=newTreeNode(“root“,n11,n12);

MyTreetree=newMyTree(root);

TreeEnumeum=tree.getEnumerator();

while(eum.hasMoreElement())

{

System.out.pr