<rt id="bn8ez"></rt>
<label id="bn8ez"></label>
  • 

    • <span id="bn8ez"></span>
    

    <label id="bn8ez"><meter id="bn8ez"></meter></label>
    

    
    

    




    







												


        



    
	
    
		
			

    

    
	
    
		
			
    Hexise's Blog
    
			業(yè)精于勤荒于嬉 行成于思?xì)в陔S
		    		
	
    

    

    

    
	
    

    posts - 13, comments - 12, trackbacks - 0, articles - 0
    
	
 
BlogJava ::
首頁(yè) ::
新隨筆 ::
聯(lián)系 ::
聚合
 ::
管理


    
		    		
	
    
	
    
		
			
    
			
    
		    		
		
			
    
				
					
	
    
		
		
    樹(shù)節(jié)點(diǎn)定義:

    class?TreeNode?{
    ????    public?TreeNode?left;

    ????    public?TreeNode?right;

    ????    public?int?value;

    ????    public?TreeNode(TreeNode?left,?TreeNode?right,?int?value)?{
    ????????    this.left?=?left;
    ????????    this.right?=?right;
    ????????    this.value?=?value;
    ????}
    }

    二叉樹(shù)及其操作:

    public?class?BinaryTree?{

    ????    public?static?int?getTreeHeight(TreeNode?root)?{
    ????????    if?(root?==?null)
    ????????????    return?0;
    ????????    if?(root.left?==?null?&&?root.right?==?null)
    ????????????    return?1;
    ????????    return?1?+?Math
    ????????????????.max(getTreeHeight(root.left),?getTreeHeight(root.right));
    ????}

    ????    public?static?void?recursePreOrder(TreeNode?root)?{
    ????????    if?(root?==?null)
    ????????????    return;
    ????????System.out.println(root.value);
    ????????    if?(root.left?!=?null)
    ????????????recursePreOrder(root.left);
    ????????    if?(root.right?!=?null)
    ????????????recursePreOrder(root.right);
    ????}

    ????    public?static?void?stackPreOrder(TreeNode?root)?{
    ????????Stack?stack?    =?new?Stack();
    ????????    if?(root?==?null)
    ????????????    return;
    ????????stack.push(root);
    ????????System.out.println(root.value);
    ????????TreeNode?temp?    =?root.left;
    ????????    while?(temp?!=?null)?{
    ????????????stack.push(temp);
    ????????????System.out.println(temp.value);
    ????????????temp?    =?temp.left;
    ????????}
    ????????temp?    =?(TreeNode)?stack.pop();
    ????????    while?(temp?!=?null)?{
    ????????????temp?    =?temp.right;
    ????????????    while?(temp?!=?null)?{
    ????????????????stack.push(temp);
    ????????????????System.out.println(temp.value);
    ????????????????temp?    =?temp.left;
    ????????????}
    ????????????    if?(stack.empty())
    ????????????????    break;
    ????????????temp?    =?(TreeNode)?stack.pop();
    ????????}
    ????}

    ????    public?static?void?recurseInOrder(TreeNode?root)?{
    ????????    if?(root?==?null)
    ????????????    return;
    ????????    if?(root.left?!=?null)
    ????????????recurseInOrder(root.left);
    ????????System.out.println(root.value);
    ????????    if?(root.right?!=?null)
    ????????????recurseInOrder(root.right);
    ????}

    ????    public?static?void?stackInOrder(TreeNode?root)?{
    ????????Stack?stack?    =?new?Stack();
    ????????    if?(root?==?null)
    ????????????    return;
    ????????    else
    ????????????stack.push(root);
    ????????TreeNode?temp?    =?root.left;
    ????????    while?(temp?!=?null)?{
    ????????????stack.push(temp);
    ????????????temp?    =?temp.left;
    ????????}
    ????????temp?    =?(TreeNode)?stack.pop();
    ????????    while?(temp?!=?null)?{
    ????????????System.out.println(temp.value);
    ????????????temp?    =?temp.right;
    ????????????    while?(temp?!=?null)?{
    ????????????????stack.push(temp);
    ????????????????temp?    =?temp.left;
    ????????????}
    ????????????    if?(stack.empty())
    ????????????????    break;
    ????????????temp?    =?(TreeNode)?stack.pop();
    ????????}
    ????}

    ????    public?static?void?main(String[]?args)?{
    ????????TreeNode?node1?    =?new?TreeNode(null,?null,?1);
    ????????TreeNode?node2?    =?new?TreeNode(null,?node1,?2);
    ????????TreeNode?node3?    =?new?TreeNode(null,?null,?3);
    ????????TreeNode?node4?    =?new?TreeNode(node2,?node3,?4);
    ????????TreeNode?node5?    =?new?TreeNode(null,?null,?5);
    ????????TreeNode?root?    =?new?TreeNode(node4,?node5,?0);
    ????????System.out.println(    "Tree?Height?is?"?+?getTreeHeight(root));
    ????????System.out.println(    "Recurse?In?Order?Traverse");
    ????????recurseInOrder(root);
    ????????System.out.println(    "Stack?In?Order?Traverse");
    ????????stackInOrder(root);
    ????????System.out.println(    "Recurse?Pre?Order?Traverse");
    ????????recursePreOrder(root);
    ????????System.out.println(    "Stack?Pre?Order?Traverse");
    ????????stackPreOrder(root);
    ????}
    }

    用LinkedList重寫的Stack:

    import?java.util.EmptyStackException;
    import?java.util.LinkedList;

    public?class?Stack?{

    ????    private?LinkedList?list;

    ????    public?Stack()?{
    ????????    this.list?=?new?LinkedList();
    ????}

    ????    public?boolean?empty()?{
    ????????    return?list.isEmpty();
    ????}

    ????    public?Object?peek()?{
    ????????    if?(empty())
    ????????????    throw?new?EmptyStackException();
    ????????    return?list.getLast();
    ????}

    ????    public?Object?pop()?{
    ????????    if?(empty())
    ????????????    throw?new?EmptyStackException();
    ????????    return?list.removeLast();
    ????}

    ????    public?void?push(Object?o)?{
    ????????list.add(o);
    ????}

    ????    public?static?void?main(String[]?args)?{
    ????????Stack?stack?    =?new?Stack();
    ????????stack.push(    new?Integer(1));
    ????????stack.push(    new?Integer(11));
    ????????stack.push(    new?Integer(1111));
    ????????stack.push(    new?Integer(22));
    ????????stack.push(    new?Integer(222));
    ????????stack.push(    new?Integer(31));
    ????????stack.push(    new?Integer(221));
    ????????    while?(!stack.empty())?{
    ????????????System.out.println(stack.pop());
    ????????}
    ????}
    }
    
	
    
	


    
	    
    

    

    評(píng)論
    
	
			
    
				
    
					
    
						# re: [復(fù)習(xí)基礎(chǔ)]Java的二叉樹(shù)遍歷操作(遞歸, 非遞歸)  回復(fù)  更多評(píng)論
						  
					
    
					2007-06-26 11:35 by Hexise
				
    
				
    [更新]加入廣度遍歷的BinaryTree:
    

     
    

    

    

    public class BinaryTree {
            public static int getTreeHeight(TreeNode root) {
                if (root == null)
                    return 0;
                if (root.left == null && root.right == null)
                    return 1;
                return 1 + Math
                    .max(getTreeHeight(root.left), getTreeHeight(root.right));
        }

            public static void recursePreOrder(TreeNode root) {
                if (root == null)
                    return;
            visit(root);
                if (root.left != null)
                recursePreOrder(root.left);
                if (root.right != null)
                recursePreOrder(root.right);
        }

            public static void stackPreOrder(TreeNode root) {
            Stack stack     = new Stack();
                if (root == null)
                    return;
            stack.push(root);
            visit(root);
            TreeNode temp     = root.left;
                while (temp != null) {
                stack.push(temp);
                visit(temp);
                temp     = temp.left;
            }
            temp     = (TreeNode) stack.pop();
                while (temp != null) {
                temp     = temp.right;
                    while (temp != null) {
                    stack.push(temp);
                    visit(temp);
                    temp     = temp.left;
                }
                    if (stack.empty())
                        break;
                temp     = (TreeNode) stack.pop();
            }
        }

            public static void recurseInOrder(TreeNode root) {
                if (root == null)
                    return;
                if (root.left != null)
                recurseInOrder(root.left);
            visit(root);
                if (root.right != null)
                recurseInOrder(root.right);
        }

            public static void stackInOrder(TreeNode root) {
            Stack stack     = new Stack();
                if (root == null)
                    return;
                else
                stack.push(root);
            TreeNode temp     = root.left;
                while (temp != null) {
                stack.push(temp);
                temp     = temp.left;
            }
            temp     = (TreeNode) stack.pop();
                while (temp != null) {
                visit(temp);
                temp     = temp.right;
                    while (temp != null) {
                    stack.push(temp);
                    temp     = temp.left;
                }
                    if (stack.empty())
                        break;
                temp     = (TreeNode) stack.pop();
            }
        }
        
            public static void widthTraverse(TreeNode root) {
            Queue queue     = new Queue();
            queue.push(root);
            traverseLevel(queue);
        }
        
            public static void traverseLevel(Queue queue){
                for(int i=0; i<queue.size(); i++){
                TreeNode node     = (TreeNode)queue.pop();
                visit(node);
                    if(node.left != null)
                    queue.push(node.left);
                    if(node.right != null)
                    queue.push(node.right);
            }
                if(queue.size() > 0)
                traverseLevel(queue);
        }

            private static void visit(TreeNode node) {
            System.out.println(node.value);
        }

            public static void main(String[] args) {
            TreeNode node1     = new TreeNode(null, null, 1);
            TreeNode node2     = new TreeNode(null, node1, 2);
            TreeNode node3     = new TreeNode(null, null, 3);
            TreeNode node4     = new TreeNode(node2, node3, 4);
            TreeNode node5     = new TreeNode(null, null, 5);
            TreeNode root     = new TreeNode(node4, node5, 0);
            System.out.println(    "Tree Height is " + getTreeHeight(root));
            System.out.println(    "Recurse In Order Traverse");
            recurseInOrder(root);
            System.out.println(    "Stack In Order Traverse");
            stackInOrder(root);
            System.out.println(    "Recurse Pre Order Traverse");
            recursePreOrder(root);
            System.out.println(    "Stack Pre Order Traverse");
            stackPreOrder(root);
            System.out.println(    "Width Traverse");
            widthTraverse(root);
        }

    }
    

    

    


    用LinkedList實(shí)現(xiàn)的Queue：
    

     
    

    

    import java.util.EmptyStackException;
    import java.util.LinkedList;

    public class Queue {
            private LinkedList list;

            public Queue() {
                this.list = new LinkedList();
        }

            public boolean empty() {
                return list.isEmpty();
        }

            public Object peek() {
                if (empty())
                    throw new EmptyStackException();
                return list.getFirst();
        }

            public Object pop() {
                if (empty())
                    throw new EmptyStackException();
                return list.removeFirst();
        }

            public void push(Object o) {
            list.add(o);
        }
        
            public int size(){
                return list.size();
        }

            public static void main(String[] args) {
            Queue queue     = new Queue();
            queue.push(    new Integer(1));
            queue.push(    new Integer(11));
            queue.push(    new Integer(1111));
            queue.push(    new Integer(22));
            queue.push(    new Integer(222));
            queue.push(    new Integer(31));
            queue.push(    new Integer(221));
                while (!queue.empty()) {
                System.out.println(queue.pop());
            }
        }
    }
    

    

    
			
    
		
			
    
				
    
					
    
						# re: [復(fù)習(xí)基礎(chǔ)]Java的二叉樹(shù)遍歷操作(遞歸, 非遞歸)  回復(fù)  更多評(píng)論
						  
					
    
					2007-09-02 14:36 by diligentjason
				
    
				
    我用generics 也寫了一個(gè)
    
			
    
		




    





    


    

	
    
		
    
				
		
	
		
    
		
		
    只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
    
		
    
			
		
    
			
		
    
		
		
    
		


    

		    		
		
    
		
    			
		
		
		
		
    
		
    
		
		
    
		
    
			網(wǎng)站導(dǎo)航:
		
		
    
		
    
			


		
    	
		
    
			 
		
    
		
    
			
		
    
		
    
			
				
		
    		
	
    	

    



    

				
			
    
		    		
	
    
	
    
		
			


		
	
    

    


    







    
        
	



主站蜘蛛池模板：
久久成人免费大片|
亚洲国产一区二区三区在线观看|
亚洲精品无码Av人在线观看国产
|
国产男女爽爽爽爽爽免费视频|
久久w5ww成w人免费|
国产在线a免费观看|
男女交性永久免费视频播放|
国产男女猛烈无遮挡免费视频网站|
全黄性性激高免费视频|
亚洲精品成人片在线观看精品字幕|
亚洲欧美成人一区二区三区|
成人在线免费视频|
西西人体免费视频|
最近新韩国日本免费观看|
久久精品夜色噜噜亚洲A∨|
狠狠色伊人亚洲综合成人|
香港特级三A毛片免费观看|
中文字幕成人免费高清在线|
7x7x7x免费在线观看|
国产成人综合亚洲亚洲国产第一页|
亚洲国产精品无码久久久|
精品久久久久亚洲|
久久久精品午夜免费不卡|
欧洲精品成人免费视频在线观看
|
亚洲91精品麻豆国产系列在线
|
一区二区三区AV高清免费波多|
四虎免费大片aⅴ入口|
亚洲日产无码中文字幕|
亚洲免费网站在线观看|
中文永久免费观看网站|
免费在线观看一级毛片|
亚洲精品美女久久7777777|
黄页网站免费观看|
亚洲精品在线免费观看视频|
窝窝影视午夜看片免费|
国产美女被遭强高潮免费网站
|
色se01短视频永久免费|
亚洲美女在线观看播放|
国产亚洲精品2021自在线|
88av免费观看入口在线|
久久精品亚洲精品国产色婷|