国产成人精品日本亚洲语音,亚洲日韩精品射精日,亚洲综合另类小说色区色噜噜

樹的非遞歸遍歷粗糙版【轉】

轉自：http://www.tkk7.com/javacap/archive/2007/10/11/152073.html
/**
*
*/

import java.util.Stack;
import java.util.Vector;

/**
* @author yovn
*
*/
public class TreeDemo {

    static interface NodeVistor
    {
         <T> void visit(BinaryTreeNode<T> node);
    }
    static class BinaryTree<T>
    {
        BinaryTreeNode<T> root;

        public BinaryTree(BinaryTreeNode<T> root) {
            this.root=root;
        }

        //no recursion ,pre-order
        void NLRVisit(NodeVistor visitor)
        {
            BinaryTreeNode<T> pointer=root;
            Stack<BinaryTreeNode<T>> stack=new Stack<BinaryTreeNode<T>>();
            while(!stack.isEmpty()||pointer!=null)
            {
                if(pointer!=null)
                {
                    visitor.visit(pointer);
                    if(pointer.rightChild!=null)
                    {
                        stack.push(pointer.rightChild);
                    }
                    pointer=pointer.leftChild;
                }
                //go to right child
                else
                {
                    pointer=stack.pop();

                }
            }
        }

        //no recursion , in-order
        void LNRVisit(NodeVistor visitor)
        {
            BinaryTreeNode<T> pointer=root;
            Stack<BinaryTreeNode<T>> stack=new Stack<BinaryTreeNode<T>>();
            while(!stack.isEmpty()||pointer!=null)
            {
                if(pointer!=null)
                {
                    stack.push(pointer);

                    pointer=pointer.leftChild;
                }
                //no left child here, then visit root and then go to right child
                else
                {
                    pointer=stack.pop();
                    visitor.visit(pointer);
                    pointer=pointer.rightChild;

                }
            }
        }


        //no recursion ,post-order,this one is the most complex one.
        //we need know from which side ,it back(left or right)
        void LRNVisit(NodeVistor visitor)
        {
            if(root==null)return;
            BinaryTreeNode<T> pointer=root;
            Stack<BinaryTreeNode<T>> stack=new Stack<BinaryTreeNode<T>>();
            while(true)
            {

                //mark left
                while(pointer!=null)
                {
                    stack.push(pointer);
                    pointer=pointer.leftChild;
                }


                pointer=stack.pop();

                while(pointer.visitedRight)//back from right child, so we can visit it now.
                {
                    visitor.visit(pointer);
                    if(stack.isEmpty())return;
                    pointer=stack.pop();
                }

                pointer.visitedRight=true;
                stack.push(pointer);

                pointer=pointer.rightChild;


            }

        }


        void levelOrder(NodeVistor visitor)
        {
            if(root==null)return;
            BinaryTreeNode<T> pointer=root;
            Vector<BinaryTreeNode<T>> queue=new Vector<BinaryTreeNode<T>>();

            queue.add(pointer);
            while(!queue.isEmpty())
            {
                BinaryTreeNode<T> node=queue.remove(0);
                visitor.visit(node);
                if(node.leftChild!=null)
                {
                    queue.add(node.leftChild);
                }
                if(node.rightChild!=null)
                {
                    queue.add(node.rightChild);
                }

            }

        }

    }
    static class BinaryTreeNode<T>
    {

        BinaryTreeNode(T data)
        {
            this.data=data;
        }
        T data;
        boolean visitedRight;
        BinaryTreeNode<T> leftChild;
        BinaryTreeNode<T> rightChild;
    }

    /**
     *
     */
    public TreeDemo() {
        // TODO Auto-generated constructor stub
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        BinaryTreeNode<String> root=new BinaryTreeNode<String>("A");
        root.leftChild=new BinaryTreeNode<String>("B");
        root.rightChild=new BinaryTreeNode<String>("C");


        root.leftChild.leftChild=new BinaryTreeNode<String>("D");

        root.rightChild.leftChild=new BinaryTreeNode<String>("E");

        root.rightChild.rightChild=new BinaryTreeNode<String>("F");

        root.rightChild.leftChild.rightChild=new BinaryTreeNode<String>("G");

        root.rightChild.rightChild.leftChild=new BinaryTreeNode<String>("H");
        root.rightChild.rightChild.rightChild=new BinaryTreeNode<String>("I");

        NodeVistor visitor=new NodeVistor()
        {

            @Override
            public <T> void visit(BinaryTreeNode<T> node) {
                System.out.print("'"+node.data+"'");

            }

        };

        BinaryTree<String> tree=new BinaryTree<String>(root);


        System.out.println("pre-order visit");
        tree.NLRVisit(visitor);
        System.out.println();
        System.out.println("in-order visit");

        tree.LNRVisit(visitor);

        System.out.println();
        System.out.println("post-order visit");

        tree.LRNVisit(visitor);

        System.out.println();
        System.out.println("level-order visit");

        tree.levelOrder(visitor);
    }

}

posted on 2009-04-15 22:03 weesun一米陽光閱讀(272) 評論(0) 編輯收藏所屬分類: JAVA源碼、總結備用

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: Java倒計時程序【收藏】 Java 倒計時【收藏】 JGA 【收藏】蟻群算法java實現[收藏] KMP算法的Java實現例子以及測試分析【收藏】用java實現RSA算法【收藏】最小二乘法擬合java實現源程序【原創】 KMP算法JAVA實現【轉】圖的深度優先搜索【收藏】關鍵路徑的java實現【收藏】

waysun一路陽光

公告

常用鏈接

隨筆分類(189)

隨筆檔案(160)

文章分類(1)

AJAX

搜索

積分與排名

最新隨筆

最新評論