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

          

          

          
	
          

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


          
		          		
	
          
	
          
		
			
          
			
          
		          		
		
			
          
				
					
	
          
		
		
          樹節(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;
          ????}
          }

          二叉樹及其操作:

          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());
          ????????}
          ????}
          }
          
	
          
	


          
	    
    

          

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




          





          


          

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


          

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


		
          	
		
          
			 
		
          
		
          
			
		
          
		
          
			
				
		
          		
	
          	

          



          

				
			
          
		          		
	
          
	
          
		
			


		
	
          

          


    







          
        
	




主站蜘蛛池模板：
桃园县|
那坡县|
洛南县|
济源市|
正安县|
神农架林区|
台湾省|
安化县|
陈巴尔虎旗|
四川省|
秀山|
莱阳市|
马山县|
衡水市|
颍上县|
禹州市|
新野县|
金川县|
蓬安县|
虞城县|
北流市|
平南县|
高唐县|
荣成市|
衡阳县|
蚌埠市|
五原县|
大厂|
龙陵县|
无棣县|
吴桥县|
营山县|
灯塔市|
丹巴县|
洪泽县|
巴楚县|
梨树县|
南投县|
井陉县|
铜陵市|
扶绥县|