<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无码国产精品麻豆天美|
99爱在线精品视频免费观看9|
亚洲熟伦熟女专区hd高清|
亚洲精品成人片在线观看|
午夜不卡久久精品无码免费|
亚洲 暴爽 AV人人爽日日碰|
亚洲中文字幕久久精品无码APP|
精品免费久久久久久久|
暖暖免费中文在线日本|
久久久无码精品亚洲日韩按摩|
国产精品免费播放|
99re热精品视频国产免费|
亚洲乱码国产乱码精华|
亚洲国产精品免费视频|
日韩精品亚洲专区在线观看|
亚洲av成人无码久久精品
|
亚洲精品你懂的在线观看|
四虎成人免费网址在线|
香港a毛片免费观看|
色多多A级毛片免费看|
亚洲1区1区3区4区产品乱码芒果|
中文国产成人精品久久亚洲精品AⅤ无码精品|
91麻豆国产免费观看|
av电影在线免费看|
亚洲人成无码网站在线观看|
亚洲真人无码永久在线|
好男人www免费高清视频在线|
男人的天堂网免费网站|
少妇亚洲免费精品|
亚洲欧美第一成人网站7777|
亚洲精品视频在线观看视频|
国产亚洲情侣一区二区无|
免费无码不卡视频在线观看|
亚洲视频免费在线看|
午夜网站在线观看免费完整高清观看
|
亚洲三区在线观看无套内射|
国产成人在线免费观看|
欧美a级成人网站免费|
亚洲免费福利视频|