二叉树的java实现

网上看到的一个二叉树，自己放到myeclipse实现了一下，但具体的在什么场景下应用还不太清楚，网上也没有找到相应的文章介绍。又重新修改了一下，还是有些地方不太明白。在建立二叉树的时候传入的数组的顺序怎么确定？一个很困扰的问题！

package algorithm;

import java.util.Stack;

/**
 * May 27, 2009 
 * version 1.1
 */

public class BinaryTree {
	  // Root node pointer. Will be null for an empty tree.
	  private Node root ;
	  private static class Node {
	      Node left ;
	      Node right ;
	      int data ;
	      Node( int newData) {
	          left = null ;
	          right = null ;
	          data = newData;
	      }
	  }
	  /**
	   Creates an empty binary tree -- a null root pointer.
	  */

	  public BinaryTree() {
	      root = null ;
	  }
	  /**
	   Inserts the given data into the binary tree.
	   Uses a recursive helper.
	  */
	  public void insert( int data) {
//		System.out.println(data);
	    root = insert( root , data);
	  }
	  /**
	   Recursive insert -- given a node pointer, recur down and
	   insert the given data into the tree. Returns the new
	   node pointer (the standard way to communicate
	   a changed pointer back to the caller).
	   二叉搜索树
	  */

	  private Node insert(Node node, int data) {		  
	    if (node== null ) {
	      node = new Node(data);
	    }else {
	      if (data <= node. data ) {
//	    	  System.out.println("left:"+data);
	        node. left = insert(node. left , data);	        
	      }else {
//		        System.out.println("right:"+data);
	        node. right = insert(node. right , data);

	      }
	    }
	    return (node); // in any case, return the new pointer to the caller
	  }

	  public void buildTree( int [] data){
	      for ( int i=0;i<data.length ;i++){
	         insert(data[i]);
	      } 

	  }

	  public void printTree() {
		  afterErgodic( root );
	      System. out .println();
	     }

	  private void printTree(Node node) {
	      if (node == null ) return ;
	      // left, node itself, right
	      printTree(node. left );
	      System. out .print(node. data + "  " );	      
	      printTree(node. right );
	     }

	  /**
	   * 先序遍历
	   * @param node
	   */
	  public void preErgodic(Node node){
		  if(node==null){
			  return;
		  }
		  Stack sk=new Stack();
		  Node p=node;
		  while(p!=null){
			  //把p节点的左子树的左子树的值获取出来
			  //把p节点的右子节点入栈，最上面的是右叶子节点
			  //栈底的节点为根的右子节点
			  while(p!=null){
				  System.out.print(p.data+" ");
				  //右子树入栈
				  if(p.right!=null) sk.push(p.right);
				  //进入下一个左子树
				  p=p.left;
			  }
			  //遍历右子树，从右叶子节点开始，然后往上，若有左子节点，则执行上面的while步骤
			  if(!sk.isEmpty()){
				  //进入下一个右子树
				  p=(Node)sk.pop();
//				  System.out.print(p.data+ " ");
			  }
		  }
	  }
	
	  /**
	   * 中序遍历
	   * @param node
	   */
	  public void centerErgodic(Node node){
		  if(node==null){
			  return;
		  }
		  Stack sk=new Stack();
		  Node p=node;
		  while(p!=null||!sk.isEmpty()){
			  //把p节点的左子节点入栈，最上面的是左叶子节点
			  while(p!=null){
				  sk.push(p);
				  p=p.left;
			  }
			  //第一步是先把左叶子节点出栈，此时右节点为null
			  //第二步是把左叶子节点的父节点出栈，此时的右节点则是右叶子节点
			  //第三步则是把左叶子节点的父节点的父节点出栈，此时右节点含有子节点
			  //第四步开始则是对右节点开始遍历，步骤则是重复前三步
			  //第五步则是重复执行第三步和第四步，直到sk里面无节点为止
			  if(!sk.isEmpty()){
				  p=(Node)sk.pop();
				  System.out.print(p.data+" ");
				  p=p.right;
			  }
		  }
	  }
	  /**
	   * 后序遍历
	   * @param node
	   */
	  public void afterErgodic(Node node){
		  if(node==null){
			  return;
		  }
		  Stack sk=new Stack();
		  Node p=node;
		  
		  while(p!=null||!sk.isEmpty()){
			  //先左后右不断深入
			  while(p!=null){
				  sk.push(p);//将根节点入栈
				  if(p.left!=null) p=p.left;
				  else p=p.right;
			  }
			  
			  //这里主要是叶子节点的获取
			  if(!sk.isEmpty()){
				  p=(Node)sk.pop();
				  System.out.print(p.data+" ");				  
			  }
			  
			  //满足条件时，说明栈顶根节点右子树已访问，应出栈访问之
			  //这里肯定是非叶子节点
			  while(!sk.isEmpty()&&((Node)sk.peek()).right==p){
				  p=(Node)sk.pop();
				  System.out.print(p.data+" ");
			  }
			  //转向栈顶根节点的右子树继续后序遍历
			  if(!sk.isEmpty()) p=((Node)sk.peek()).right;
			  else p=null;			  
		  }
	  }
	  
	  /**
	   * 另外一种建立二叉树的方法，非递归形式
	   * @param data
	   */
	  public void createBinary(int[] data){
		  Node temp = null; 		  
		  for(int i=0;i<data.length;i++){
			  // 创建根节点 
			  if(root==null){
				  root = temp = new Node(data[i]); 
			  }else{
				// 回到根结点
				  temp=root;
				  // 添加节点   
				  while (temp.data != data[i]) {   
					  if(temp.data>data[i]){//左子树						  
						  if (temp.left != null) {
//							  System.out.println(data[i]+" "+22);
					          //如果有左子树，则把左子树赋值给temp，此次while循环结束，开始下次循环。
							  //直到没有左子树为止，即新增加一个左子树
							  temp = temp.left;
						  }else{
					          //新增左子树
//							  System.out.println(data[i]+" "+11);
							  temp.left=new Node(data[i]);
							  //这里可以减少循环的次数，新增之后再判断时则会跳出循环
							  temp = temp.left;
						  }
					  }else{//右子树
						  if(temp.right!=null){
							  //同左子树
							  temp = temp.right;  
						  }else{
							  temp.right=new Node(data[i]);
							  //同上
							  temp = temp.right;  
						  }
					  }
				  }
			  }		  
		  }
//		  return root;
	  }
	  
	  
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		BinaryTree bt=new BinaryTree();
		//数据貌似不能是排好序的，但必须有顺序，貌似是前序遍历的顺序
		int[] array={4, 2, 6, 1, 3, 5, 7};
//		bt.buildTree(array);
		bt.createBinary(array);
		bt.printTree();
//		#      4
//		#    /    \
//		#   2      6
//		#  / \    / \
//		# 1  3   5   7 
//		# 前序遍历：4 2 1 3 6 5 7   
//		# 中序遍历：1 2 3 4 5 6 7   
//		# 后序遍历：1 3 2 5 7 6 4   
	}

}

评论

1 楼 liuyuanhui0301 2012-07-02