binarytree.java

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

//普通二叉树类
package com.fluently.DataStructure;
import java.io.*;
import com.fluently.DataStructure.*;

public class BinaryTree{
	//二叉树的起点
	public BinaryTreeNode root;
	//存储信息
	public BinaryTreeNode [] Mem;
	
	public int NumOfNodes;
	//构造方法
	public  BinaryTree(int num)
	{
	this.NumOfNodes=num;
	this.Mem=new BinaryTreeNode[num];
	this.root=null;
	}
	//基于二叉完全树的标号来建立二叉树
	public void BuildTree()
	{
		int id=0;int child=0;
		 //从终端上输入结点信息
		BufferedReader readStream=new BufferedReader (new InputStreamReader (System.in));
		//依次输入接点信息
		//从根结点开始
		for (int i=1;i<NumOfNodes ;i++ )
		{
			// 提示输入
			while (true)
			{
				System.out.print("请输入结点编号:"+"特别注意1为根,0为放弃本接点的输入");
				try
				{
					id=Integer.parseInt(readStream.readLine());
				}
				catch (IOException e)
				{
				}
				catch(NumberFormatException e)
				{
				continue;
				
				}
				if (id<0||id>=NumOfNodes)
				{
					System.out.println("结点编号超出范围，重新输入");
						continue;
				}
				break;


			}
			//如果放弃本站点，则继续输入下一个站点 
			if (id==0)
			{
				continue;
			}
			//新建一个站点
			 BinaryTreeNode newNode=new BinaryTreeNode(id);
			 //根据定义设置指针
			 Mem[id]=newNode;
			 if (id==1)
			 {
				 root=newNode;

			 }
			 else
			{
				 child=id/2;
				 if (id%2==0)
				 {
					 Mem[child].left=newNode;
					 
				 }
				 else
				Mem[child].right=newNode;
		    }
		}
	
	}
	//中序遍历方法
	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 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 void printTree(BinaryTreeNode localRoot)
{
//如果localRoot是根
if (localRoot==root)
{
	System.out.print("二叉树的广义表如下;");
	System.out.print("");
	System.out.print(localRoot.id);
	//处理左子女
	if (localRoot.left!=null)
	{
		System.out.print(",(");
		printTree(localRoot.left);
		System.out.print(")");


	}
//处理右子女
if (localRoot.right!=null)
{
	System.out.print(",(");
	printTree(localRoot.right);
	System.out.print(")");

}
System.out.print(")");
}
//如果不是跟
if (localRoot!=root)
{
	System.out.print(localRoot.id);
	if (localRoot.left!=null)
	{
		System.out.print(",(");
		printTree(localRoot.left);
		System.out.print(")");
	}
	if (localRoot.right!=null)
	{
		System.out.print(",(");
		printTree(localRoot.right);
		System.out.print(")");
	}
}



}

}