balancedtree.java

这是数据结构中的描述二叉树的一个JAVA 程序。

//平衡二叉树
package com.fluently.DataStructure;
import com.fluently.DataStructure.*;
public class  BalancedTree
{
	public BalancedNode root;
	public BalancedTree() 
	{
		this.root=root;
	}
	//insetintobalanced方法
	//1。创建一个节点，将带插入元素复制给此节点
	//2。遍历树，
	//找到新节点在书中位置
	//将新节点插入书中
	//回溯到根节点的路径，该路径数为查找新节点在书中位置而建立
	boolean isTaller;
	private BalancedNode insertIntoBalanced(BalancedNode root,BalancedNode newNode)
	{
		if (root==null)
		{
			root=newNode;
			isTaller=true;
		}
		else
			if (root.value==newNode.value)
			System.out.println(" 没有适当位置");
		else 
			if (root.value>newNode.value)     //进入左子树
			{
				root.left=insertIntoBalanced(root.left,newNode);
				if(isTaller)                //插入后左子树变高
				switch(root.bfactor){
					case -1:root=balanceFromLeft(root);
					         isTaller=false;
							 break;
					case 0: root.bfactor=-1;
					        isTaller=true;
					         break;
                    case 1: root.bfactor=0;
					            isTaller=false;
				}                        //end switch
			}     //end if
			else{
				root.right=insertIntoBalanced(root.right,newNode);
				if(isTaller)                //插入后右子树变高
				switch(root.bfactor){
					case -1:root.bfactor=0;
					         isTaller=false;
							 break;
					case 0: root.bfactor=1;
					        isTaller=true;
					         break;
                    case 1: root=balanceFromRight(root);
					            isTaller=false;
				}                        //end switch
					 
			} //end else
			return root;
	}//end insertIntoBalanced
	public void insert(int num)
	{
		isTaller=false;
		BalancedNode newNode;

		newNode=new BalancedNode(num);
		newNode.value=num;
		newNode.bfactor=0;
		newNode.left=null;
        newNode.right=null;
		root=insertIntoBalanced(root,newNode);
	}
	//调整树，使平衡
	//左旋转
	private BalancedNode rotateToLeft(BalancedNode root)
	{
		BalancedNode p;  //指向右子树根节点
		if (root==null)
			System.err.println("错误");
		else
		  if(root.right==null)
		            System.err.println("错误：没有右子树");
		  else{
			p=root.right;
			root.right=p.left; //左子树根节点p成为右子树根节点
			p.left=root;
			root=p;               //p重新指向新的根节点
		}//end else
		return root;
		}//end rotateToLeft
   private BalancedNode rotateToRight(BalancedNode root){
	   BalancedNode p;  //指向左子树根节点
		if (root==null)
			System.err.println("错误");
		else
		  if(root.left==null)
		            System.err.println("错误：没有左子树");
		  else{
			p=root.left;
			root.left=p.right; //右子树根节点p成为左子树根节点
			p.right=root;
			root=p;               //p重新指向新的根节点
		}//end else
		return root;
   }
   //方法balance利用上述令方法在特定节点实现树的重构，同时调整由于重构而变化的平衡因子bfactor
   //balanceFromLeft子树是双倍作糕须经特定节点移至右子树
   private BalancedNode balanceFromLeft(BalancedNode root)
   {
	   BalancedNode p; 
	   BalancedNode w;
	   p=root.left;  //p指向左子树根节点
       switch(p.bfactor){
			case -1:root.bfactor=0;
					p.bfactor=0;
				    root=rotateToRight(root);
					         break;
			case 0: System.err.println("错误:无法从左边平衡");

                     break;
             case 1:w=p.right;
			         switch(root.bfactor){
			               case -1:root.bfactor=1;
					              p.bfactor=0;
							  break;
							case 0:root.bfactor=0;
							        p.bfactor=0;
                                    break;

                           case 1:root.bfactor=0;
                              p.bfactor=-1;
	                    }//end switch
	    w.bfactor=0;
		p=rotateToLeft(p);
		root.left=p;
		root=p=rotateToRight(root);
        }//end switch
        return root;
   }
    private BalancedNode balanceFromRight(BalancedNode root)
   {
	   BalancedNode p; 
	   BalancedNode w;
	   p=root.right;  //p指向右子树根节点
       switch(p.bfactor){
		   case -1:w=p.left;
			         switch(root.bfactor){
			               case -1:root.bfactor=0;
					              p.bfactor=1;
							  break;
							case 0:root.bfactor=-1;
							        p.bfactor=0;
                                    break;

                           case 1:root.bfactor=-1;
                              p.bfactor=0;
	                    }//end switch
			            w.bfactor=0;
		              p=rotateToRight(p);
		              root.right=p;
		              root=p=rotateToLeft(root);
					         break;
			case 0: System.err.println("错误:无法从右边平衡");
                     break;
			case 1:root.bfactor=0;
					p.bfactor=0;
				    root=rotateToLeft(root);
             
	   
        }//end switch
        return root;
   }
//中序遍历方法
	public void inOrder(BalancedNode localRoot)
{
		if (localRoot!=null)
		{
			inOrder(localRoot.left);
			localRoot.displayNode();
			inOrder(localRoot.right);

		}
	
	
}
//前序遍历方法
public void proOrder(BalancedNode localRoot)
{
		if (localRoot!=null)
		{
			localRoot.displayNode();
			proOrder(localRoot.left);
			proOrder(localRoot.right);
		}

}
//后序遍历方法
public void postOrder(BalancedNode localRoot)
{
		if (localRoot!=null)
		{
			postOrder(localRoot.left);
			postOrder(localRoot.right);
			localRoot.displayNode();
		}


}


	


}