waysun一路陽光

不輕易服輸,不輕言放棄.--心是夢的舞臺，心有多大，舞臺有多大。踏踏實實做事，認認真真做人。

BlogJava :: 首頁 :: 新隨筆 :: 聯系 :: :: 管理 ::

167 隨筆 :: 1 文章 :: 64 評論 :: 0 Trackbacks

<

2009年4月

>

日

一

二

三

四

五

六

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

7

8

9

公告

開啟一扇窗,給自己一個舞臺!

QQ:251218333,82424805
MSN:CF1504@Hotmail.com
E-mail:yyk1504@163.com
第位來訪者

常用鏈接

隨筆分類(189)

隨筆檔案(160)

文章分類(1)

AJAX

Flex
iDEAL網絡
Java開源AJAX框架
nm1504
struts
亮亮的博客
沖出宇宙
周老師科研站
四海兄弟
我的休閑博客
方佳瑋的博客
昆山人在上海
空山雪林
胡偉的官方博客
舞動JAVA
趙良乾

搜索

積分與排名

積分 - 237164
排名 - 239

最新評論

1.?re: cfca證書工具包使用指南【轉】
阿斯頓撒旦
--廖
2.?re: Java源碼：md5加密算法（轉帖）
11111111111111111111111
--企鵝額
3.?re: javascript中獲取radio值得方法【收藏】
范德薩發大水
--俄方地方
4.?re: 模態窗口提交到struts2的action后關閉自身并返回到父窗口，父窗口為一個iframe[未登錄]
頂頂頂頂
--斷點
5.?www
11
--ww

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

轉自：http://www.aygfsteel.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一米陽光閱讀(278) 評論(0) 編輯收藏所屬分類: JAVA源碼、總結備用

新用戶注冊刷新評論列表


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




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