JAVA技巧(java實(shí)現(xiàn)二叉樹前序遍歷迭代器)

關(guān)鍵就是要用一個(gè)棧來保存遍歷路徑。主要涉及類如下：
    class TreeNode 這個(gè)類用來聲明樹的結(jié)點(diǎn)，其中有左子樹、右子樹和自身的內(nèi)容。
    class MyTree 這個(gè)類用來聲明一棵樹，傳入根結(jié)點(diǎn)。這里設(shè)計(jì)的比較簡單
    class TreeEum 這個(gè)類是樹的迭代器，通過MyTree類的方法獲取，這里主要就是設(shè)計(jì)它了。代碼如下：
    //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類，沒什么功能，傳入根結(jié)點(diǎn)構(gòu)造，getEnumerator()方法獲取迭代器。
    class MyTree
    {
    TreeNode root;
    public MyTree(TreeNode root)
    {
    this.root=root;
    }
    public TreeEnum getEnumerator()
    {
    return new TreeEnum(root);
    }
    }
    //這個(gè)類為迭代器，有詳細(xì)解釋，相信各位能看懂。在棧中用了兩次泛型。
    import java.util.Stack;
    public class TreeEnum
    {
    private TreeNode root;
    private Stack> store;/*保存遍歷左子樹但未遍歷右子樹的結(jié)點(diǎn)*/
    private TreeNode next;
    public TreeEnum(TreeNode root)
    {
    this.root=root;
    store=new Stack>();
    next=root;
    }
    public TreeNode next()
    {
    TreeNode current=next;
    if(next!=null)
    {
    /*如果當(dāng)前結(jié)點(diǎn)的左子樹不為空,則遍歷左子樹,并標(biāo)記當(dāng)前結(jié)點(diǎn)未遍歷右子樹*/
    if(next.left()!=null)
    {
    store.push(next);
    next=next.left();
    }
    //如果當(dāng)前結(jié)點(diǎn)的左子樹為空,則遍歷右子樹
    else if(next.right()!=null)
    {
    next=next.right();
    }
    /*如果當(dāng)前結(jié)點(diǎn)為葉子,則找未遍歷右子樹的結(jié)點(diǎn)并且遍歷它的右子樹*/
    else{
    if(!store.empty())/*判斷是否還有結(jié)點(diǎn)的右子樹未遍歷*/
    {
    TreeNode tmp=store.pop();
    /*如果有未遍歷右子樹的結(jié)點(diǎn),但它的右子樹為空,且還有結(jié)點(diǎn)的右子樹未遍歷,*/
    /*則一直往上取,直到取到未遍歷右子樹且右子樹不為空的結(jié)點(diǎn),遍歷它的右子樹.*/
    while((tmp.right()==null)&&!store.empty())
    {
    tmp=store.pop();
    }
    next=tmp.right();
    }
    else
    {
    /*如果沒有哪個(gè)結(jié)點(diǎn)右子樹未遍歷,則表示沒有下一個(gè)結(jié)點(diǎn)了,設(shè)置next為null*/
    next=null;
    }
    }
    }
    return current;
    }
    public boolean hasMoreElement()
    {
    return next!=null;
    }
    }
    下面寫個(gè)測試類，不作解釋，相信大家看得懂
    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");
    }
    }
    由于急著實(shí)現(xiàn)迭代器，所以沒有去實(shí)現(xiàn)其他功能，迭代器類寫的也匆忙，還有很多可改進(jìn)的地方，考試大希望各位朋友可以提出意見和建議。