binarysorttree.java

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

//排序二叉树
package com.fluently.DataStructure;

public class BinarySortTree extends BinaryTree
{

	
	//构造方法
	public BinarySortTree()
	{
		super(0);
	
	}
	
	//在二叉排序树中插入指定值得方法
	public void insertNode(BinaryTreeNode inputData)
	{
		 //新建一个站点
		BinaryTreeNode newNode=inputData;
		//判断是否为空树 
		 if (root==null)
		{
			root=newNode;

		}
		else//不适空的二叉树
		{
			//从根开始定位
			BinaryTreeNode current=root;
			//申请临时工作站点
			BinaryTreeNode parent;
			//开始定位操作
			while (true)
			{
				//存储相对夫节点
				parent=current;
				//判断是否走作节点
				if (inputData.id<current.id)
				{
					current=current.left;
					//是否到达也节点
					if (current==null)
					{
						//插入节点作为作节点
						parent.left=newNode;
						return;
					}

				}//作节点结束
					else
					{
						//走有节点
						current=current.right;
						//是否走到也节点
						 if (current==null)
						 {
							//作为有节点插入
							 parent.right=newNode;
							return;
						 }

					}//有节点操作结束
			}//结束循环
		}//不适非空二叉树处理结束
	}
		
		//返回 delNode右子女中最小值中，然后是右子女的后代
		/*public  BinaryTreeNode getSuccessor (BinaryTreeNode  delNode)
		{
			BinaryTreeNode successorParent=delNode;
			BinaryTreeNode  successor=delNode;
			//进入右子女
			BinaryTreeNode current=delNode.right;
			//查找右子女子树
			while (current!=null)
			{
				//左子女
				successorParent=successor;
				successor=current;
				//进入左子女
				current=current.left;

			}
		   //如果没有后继接点
		   if (successor!=delNode.right)
		   {
			   //建立连接
			   successorParent.left=successor.right;
			   successor.right=delNode.right;

		   }
		   return  successor;
        }*/
		// 删除结点的方法
		//删除存储指定关键值的结点
		/*public boolean delete(int key)
{
		//假设是一个非空列表
		treeNode current=root;
		treeNode parent=root;
		boolean LeftChild=true;
		//定位结点
		while (current.data.id)
		{
			parent=current;
			//转向左子树
			if (key<current.data.id)
			{
				isLeftChild=false;
				current=current.leftChild;

			}
			else//转向右子树 
			{
			isLeftChild=false;
			current=current.rightChild;
			}
			//还没找到
			if (current==null)
			{
				return false;
			}
		}
			//end while
			//找到了要删除的结点
			//继续操作
			//如果没有子女接点，简单删除
			if (current.leftChile==null&&current.rightChild==null)
			{
				//删除结点是否为root
				if (current==null)
				{
					root=null;
					//清空二叉树

				}
				else if (isLeftChile)
				{
					parent.leftChild=null;
				}
				else 
					parent.rightChilf=null;
			}
			//如果没有右子女，用左子树代替
			else if (current.rightChild==null)
			{
				if (current==root)
				
					root=current.leftChild;

				
				else if (isLeftChild)//左子树的父接点
				{
				parent.leftChild=current.leftChild;
				}
				else //右子树的父接点
				parent.rightChild=current.leftChild;
			}
				//如果没有左子数，就用右子树代替
				 if (current.leftChild==null)
				{
					if (current==root)
					{
						root=current.rightChild;


					}
					else if (isLeftChild)//左子树的父结点
					{
						parent.leftChild=current.rightChild;
						
					}
					else //右子树的父结点
					parent.rightChild=current.rightChild;
				}
					//继续
					//delete()continued
					else  //两个子女接点。替换中序后继者
				  {
					//获得要删除接点current的后继者
					treeNode successor=getSuccessor(current);
					//连接current的父结点到successor
					if (current==root)
					{
						root=successor;

					}
					else if (isLeftChild)
					{
						parent.leftChild=successor;

					}
					else 
						parent.rightChild=successor;
					//连接successor到current的左子女
					successor.leftChild=current.leftChild;
				}
					//end else two children
					//(后继不能没有左子女)
					return true;
             }
					//end delete

}*/
	//中序遍历方法
	public void inOrder(BinaryTreeNode localRoot)
{
		if (localRoot!=null)
		{
			inOrder(localRoot.left);
			localRoot.displayNode();
			inOrder(localRoot.right);

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

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


}


//深度
public int height(BinaryTreeNode p)
	
{
	
	
	if(p==null)
			
     return 0;
	
  		else
	{
	int l=height(p.left);
    int r=height(p.right);
		 if (l>=r )
		{
		   return  l+1;
		}
		else
		
		{
			return r+1;
		}
    }
}
	public int treeHeight()
	{
	
		return height(root);
	} 


	

	
//结点数
public  int nodeCount(BinaryTreeNode p)
{
		int nodeCount=0;
		if ( p==null)
		
			  return 0;
	else{
		if (p.left==null&&p.right==null)
		    return 1;

		
	     else 
			 return nodeCount(p.left)+nodeCount(p.right)+1; 
			

		}
	
}
public int treeNodeCount()
	{
	
		return nodeCount(root);
	} 


	
	//查找
	//查找自定关键值得结点
public BinaryTreeNode find(int key)
{
//假设是一个非空的树 
//从根节点开始
BinaryTreeNode current=root;
//当关键之不匹配时,反复执行
while (true)
{
	if (current.id==key)
	{
	break;
	
	}
	//判断是否进入子树 
	if (key<current.id)
	{
		current=current.left;
	}
		else
		current=current.right;//进入由子树
		//如果没有子树
		if (current==null)
		{
			return null;
			

		}
		}
		//发现存储制定关键值得节点
		return current;
		

}

/**

//判断是否是满二叉树
public boolean  full(BinaryTreeNode p)
{  if  ( p!= null)
         if  ( p.left == null && p.right ==null)
             return  true;
         else  if  (p.left ==null || p.right == null)  
                      return false;
                  else
					  return( full(p.left ) && full( p.right ));
}

**/




}