java 实现完全二叉树

2016-08-16
/**  * 树的节点  **/ package DataStructure;  /**  * Copyright 2014 by Ruiqin Sun  * All right reserved  * created  on 2014-9-9 下午5:05:13  **/  	public class TreeNode{ 		private int value; 		private TreeNode leftNode; 		private TreeNode rightNode; 		/** 		 * @return the value 		 */ 		public int getValue() { 			return value; 		} 		/** 		 * @param value the value to set 		 */ 		public void setValue(int value) { 			this.value = value; 		} 		/** 		 * @return the leftNode 		 */ 		public TreeNode getLeftNode() { 			return leftNode; 		} 		/** 		 * @param leftNode the leftNode to set 		 */ 		public void setLeftNode(TreeNode leftNode) { 			this.leftNode = leftNode; 		} 		/** 		 * @return the rightNode 		 */ 		public TreeNode getRightNode() { 			return rightNode; 		} 		/** 		 * @param rightNode the rightNode to set 		 */ 		public void setRightNode(TreeNode rightNode) { 			this.rightNode = rightNode; 		} 	}  

/**  * 队列  **/ package DataStructure;  import java.util.LinkedList;  /**  * Copyright 2014 by Ruiqin Sun  * All right reserved  * created  on 2014-9-9 下午5:06:46  **/ public class Queue { 	private LinkedList<TreeNode> list;  	/** 	 * @return the list 	 */ 	public LinkedList<TreeNode> getList() { 		return list; 	}  	/** 	 * @param list the list to set 	 */ 	public void setList(LinkedList<TreeNode> list) { 		this.list = list; 	}  	 public Queue(){ 		 list = new LinkedList<TreeNode>(); 	 }  	  	 public void inQueue(TreeNode node){ 		 list.add(node); 	 } 	  	 public TreeNode outQueue(){ 		return list.removeFirst(); 	 } 	  	 public boolean isEmpty(){ 		return list.isEmpty(); 	 } } 

/**   * 构建完全二叉树   **/  package DataStructure;    import java.util.ArrayList;  import java.util.Scanner;      /**   * Copyright 2014 by Ruiqin Sun   * All right reserved   * created  on 2014-9-9 下午4:19:24   **/    public class CompleteBinTree {        private TreeNode root;      private Queue queue;                /**       * @return the queue       */      public Queue getQueue() {          return queue;      }        /**       * @param queue the queue to set       */      public void setQueue(Queue queue) {          this.queue = queue;      }        /**       * @return the root       */      public TreeNode getRoot() {          return root;      }        /**       * @param root the root to set       */      public void setRoot(TreeNode root) {          this.root = root;      }           public CompleteBinTree(){          root = null;      }  //插入节点      public  void insertNode(TreeNode node){          if(root == null){              this.setRoot(node);          }else{              queue = new Queue();              queue.inQueue(root);              while(!queue.isEmpty()){                  TreeNode temp = queue.outQueue();                  if(temp.getLeftNode() == null){                      temp.setLeftNode(node);                      return;                  }else if(temp.getRightNode() == null){                      temp.setRightNode(node);                      return;                  }else{                      queue.inQueue(temp.getLeftNode());                      queue.inQueue(temp.getRightNode());                  }              }          }      }// end insertNode            /*       *前序遍历二叉树       * */      public void preOrder(TreeNode node){          if(node != null){              System.out.print(node.getValue());              preOrder(node.getLeftNode());              preOrder(node.getRightNode());          }      }      /*       *中序遍历二叉树       * */      public void inOrder(TreeNode node){          if(node != null){              inOrder(node.getLeftNode());              System.out.print(node.getValue());              inOrder(node.getRightNode());          }      }      /*       *后序遍历二叉树       * */      public void postOrder(TreeNode node){          if(node != null){              postOrder(node.getLeftNode());                          postOrder(node.getRightNode());                  System.out.print(node.getValue());          }      }      /**       * @param args       */      public static void main(String[] args) {          // TODO Auto-generated method stub        System.out.println("请输入要排序的数组,数字之间用"+","+"隔开:");          Scanner scan = new Scanner(System.in);          String s= scan.nextLine();          String[] list= s.split(",");          CompleteBinTree combinTree = new CompleteBinTree();          for(String i : list){              TreeNode node = new TreeNode();              node.setValue(Integer.parseInt(i));              combinTree.insertNode(node);          }            System.out.println("前序遍历:");          combinTree.preOrder(combinTree.root);          System.out.println("");          System.out.println("中序遍历:");          combinTree.inOrder(combinTree.root);          System.out.println("");          System.out.println("后序遍历:");          combinTree.postOrder(combinTree.root);      }        }