usebinarytree.java

有大量的java的实例

public class UseBinaryTree //定义主类，创建、遍历、查找二叉树
{
  public static void main(String args[])
  {
   int[] dataIn = {49,45,80,11,18,106,55,251,91}; //欲放入二叉树中的数据
   int key1,key2;		//欲查找的数据
   BinaryTree searchTree = new BinaryTree(dataIn[0]);	//创建二叉树
   if(args.length<2)	//要求提供2个命令行参数
   {
	System.out.println("请同时输入2个整型命令行参数");
	System.exit(0);
   }
   for(int i=1;i<dataIn.length;i++)
     searchTree.insertToTree(dataIn[i]);	//将数据加入二叉树
   System.out.print("先序遍历结果：");
   System.out.println(searchTree.preOrderReview());
   System.out.print("中序遍历结果：");
   System.out.println(searchTree.inOrderReview());
   System.out.print("后序遍历结果：");
   System.out.println(searchTree.postOrderReview());
   key1 = Integer.parseInt(args[0]);
   key2 = Integer.parseInt(args[1]);
   System.out.println("在树中查找数据 " + key1 + ":   " 
                          + searchTree.searchData(key1));
   System.out.println("在树中查找数据 " + key2 + ":   " 
                          + searchTree.searchData(key2));
  }
}
//==============================================================
class BinaryTree			//二叉树类
{
   TreeNode m_RootNode;				//根节点

   BinaryTree(int rootdata)	//构造函数，创建二叉树及其根节点
   {
	m_RootNode = new TreeNode(rootdata);
   }

   void insertToTree(int newdata)		//将一个新数据插入二叉树
   {
	m_RootNode.insertNode(newdata);
   }

   String preOrderReview()  //先序遍历整棵树，与下面的方法形成方法的重载
   {	
	return preOrderReview(m_RootNode);
   }

   String preOrderReview(TreeNode subRoot) //先序遍历以subRoot为根节点的子树
   {
	String s="";
	if(subRoot==null)
        	return s;		//递归头
	else
	{
         s = s + subRoot.getData() + "; ";//先访问当前根节点
	 s = s + preOrderReview(subRoot.getLeftPoint()); //然后是左子树
         s = s + preOrderReview(subRoot.getRightPoint());//然后是右子树
         return s;
	}
   }
	
   String inOrderReview()//中序遍历整棵树
   {
	return inOrderReview(m_RootNode);
   }
	
   String inOrderReview(TreeNode subRoot)  //中序遍历以subRoot为根节点的子树
   {
	String s="";
	if(subRoot==null)
		return s;//递归头
	else
	{
         s = s + inOrderReview(subRoot.getLeftPoint());	//先访问左子树
 	 s = s + subRoot.getData() + "; ";  	//再访问当前根节点
	 s = s + inOrderReview(subRoot.getRightPoint());//最后访问右子树
	 return s;
	}
   }

   String postOrderReview()//后序遍历整棵树
   {
	return postOrderReview(m_RootNode);
   }

   String postOrderReview(TreeNode subRoot) //后序遍历以subRoot为根节点的子树
   {
	String s="";
	if(subRoot==null)
		return s;//递归头
	else
	{
	 s = s + postOrderReview(subRoot.getLeftPoint());//先访问左子树
	 s = s + postOrderReview(subRoot.getRightPoint());//再访问右子树
	 s = s + subRoot.getData() + "; ";	//最后访问当前根节点
	 return s;
	}
   }
	
   String searchData(int key)	//查找整棵二叉树中与key匹配的数据
   {
	return searchData(m_RootNode,key);
   }

   String searchData(TreeNode subRoot,int key)
                           //在subRoot为根节点的子树中查找key
   {
	String s = "未找到；";
	if(subRoot == null)
  	  return s;		//递归头1：未找到
	else
	{
	 s = subRoot.getData() + "; ";
 	 if(key == subRoot.getData())		//递归头2：找到
	  return s + "找到";
	 else if(key > subRoot.getData())
	  return s + searchData(subRoot.getRightPoint(),key);//向右子树查找
	 else 
	  return s + searchData(subRoot.getLeftPoint(),key);//向左子树查找
	}
   }
}
//===============================================================
class TreeNode		//二叉树的节点类
{
  TreeNode m_LeftPoint;  				//左指针
  TreeNode m_RightPoint; 				//右指针
  private int m_Data;				//节点中的数据

  TreeNode(int newdata)					//构造函数
  {
	m_Data = newdata;
	m_LeftPoint = null;
	m_RightPoint = null;
  }

  int getData()
  {
	return m_Data;
  }

  void setData(int newdata)
  {
	m_Data = newdata;
  }

  TreeNode getLeftPoint()
  {
	return m_LeftPoint;
  }

  TreeNode getRightPoint()
  {
	return m_RightPoint;
  }

  void insertNode(int newdata)
  {	//使用递归方法将一个新节点插入在以当前节点为根节点的二叉树上
	if(newdata>=getData())
	{	//将大于等于当前数据的新节点安排在右子树
		if(m_RightPoint == null)
		  m_RightPoint = new TreeNode(newdata);	//递归头
		else
		m_RightPoint.insertNode(newdata);		//递归调用
	}
	else
	{	//将小于当前数据的新节点安排在左子树
		if(m_LeftPoint == null)
			m_LeftPoint = new TreeNode(newdata);	//递归头
		else
			m_LeftPoint.insertNode(newdata);//递归调用
	}
  }
}