查询二叉树的兑现

查询二叉树的实现

首先是Node 类的定义

package SearchTree;

public class Node {

	private Node left;
	private Node right;
	private Node Parrent;
	
	int data;

	public Node(Node left, Node right, Node parrent, int data) {
		super();
		this.left = left;
		this.right = right;
		Parrent = parrent;
		this.data = data;
	}

	
	public void setLeft(Node left) {
		this.left = left;
	}


	public void setRight(Node right) {
		this.right = right;
	}


	public void setParrent(Node parrent) {
		Parrent = parrent;
	}


	public void setData(int data) {
		this.data = data;
	}


	public Node getLeft() {
		return left;
	}

	public Node getRight() {
		return right;
	}

	public Node getParrent() {
		return Parrent;
	}

	public int getData() {
		return data;
	}
	
}

接着是，Tree 类的定义（各种常用的操作）

package SearchTree;

public class Tree {

	private Node boot=null;  // 二叉查找树的根节点

	public Node getBoot() {
		return boot;
	}

	public void setBoot(Node boot) {
		this.boot = boot;
	}
	
	public void Tree_Insert(Node i_node)    // 在树中插入一个节点 i_node
	{
		Node y = null;
		Node x = boot;
		
		while(x!=null)
		{
			y = x;
			if(i_node.getData() < x.getData())
				x = x.getLeft();
			else x = x.getRight();
		}
		
		i_node.setParrent(y);  // 设置插入节点的 父节点
		
		if(y == null) // This Tree is empty;
		{
			boot = i_node;
		}
		else if(y.getData() > i_node.getData())
			y.setLeft(i_node);
		else y.setRight(i_node);
	}
	public void InOrder_Tree_Walk()   // 中序遍历输出树
	{
		Traversal(boot);
	}
	private void Traversal(Node x)
	{
		if(x!=null)
		{
			Traversal(x.getLeft());
			System.out.println(x.getData());
			Traversal(x.getRight());
		}
	}
	
	public Node Tree_Search(int data)
	{
//		Node find =RecursionSearch(boot, data);        // 递归的查找
		Node find = Non_RecursionSearch(boot, data);   // 非递归的查找
		if(find == null)
			System.out.println("Warning:The element that you are searching is not in the tree!");
		else System.out.println("find the element in the tree!");
		return find;
	}
	
	private Node RecursionSearch(Node b,int data)
	{
		if(b==null || b.getData()==data)  // | 和 || 两者之间什么关系 ？
			return b;
		
		if(b.getData() < data)
			return RecursionSearch(b.getRight(), data);
		else return RecursionSearch(b.getLeft(), data);
	}
	
	private Node Non_RecursionSearch(Node b,int data) // 非递归的查找的实现
	{
		while(b!=null && b.getData()!=data)
		{
			if(b.getData() > data)
				b = b.getLeft();
			else b = b.getRight();
		}
		return b;
	}
	/***
	 * 返回树中最小的元素 ，如果树为空的话，返回空的引用
	 * @return
	 */
	public Node Tree_Minmum() 
	{
		if(boot==null)
			return null;
		Node find = minmum(boot);
		return find;
	}
	private Node minmum(Node x)
	{
		while(x.getLeft()!=null)
			x= x.getLeft();
		return x;
	}
	/**
	 * 返回树中最大的元素，如果树为空的话，返回空的引用
	 * @return
	 */
	public  Node Tree_Maximum()
	{
		if(boot == null)
			return boot;
		Node find = Maximum(boot);
		return find;
	}
	private Node Maximum(Node x)
	{
		while(x.getRight()!=null)
			x = x.getRight();
		return x;
	}
	/**
	 * 查找一个给定元素data的后继（如果该元素存在的话）
	 * 存在两种情景:1：存在右孩子，则求右孩子的minmum即可
	 *           2: 不存在右孩子，那么向上循环查找一个父节点，它的左孩子等于循环中的x，此时该点为其后继 
	 * @param data
	 * @return
	 * while 循环是本函数的核心代码（难点）
	 */
	public Node Tree_Successor(int data)
	{
		Node x= Tree_Search(data); // 获得元素data 的节点引用。
		if(x==null) return null;
		
		if(x.getRight()!=null)
			return minmum(x.getRight());
		
		Node y = x.getParrent();
		
		while(y!=null && x==y.getRight())
		{
			x=y;
			y= y.getParrent();
		}
		
		return y;
	}
	/**
	 * Funtion:查找一个给定元素的中序遍历的前驱节点，有两种情况：
	 * 1:该节点存在左孩子，那么求左孩子的Maximum
	 * 2:该节点没有左孩子，那么向上递归求（通过循环）一个存在右孩子的节点，即为所求节点的前驱节点
	 * @param data
	 * @return
	 */
	public Node Tree_Predecessor(int data)
	{
		Node x = Tree_Search(data); // 获得元素data 的引用
		if(x==null) return null;
		
		if(x.getLeft()!=null) // 第一种情况，存在左孩子
			return Maximum(x.getLeft());
		
		Node y = x.getParrent();
		while(y!=null && y.getLeft()==x)
		{
			x=y;
			y= y.getParrent();
		}
		return y;
	}
	/**
	 * funtion:删除树中的元素data(如果存在的话)，删除时存在三种情况：
	 * 1：该节点没有孩子节点，则，直接删除
	 * 2：该节点有一个孩子节点，那么删除节点之后，将该节点的父节点执行该节点的子节点
	 * 3：存在两个子节点，那么将该节点的后继，覆盖带该节点即可，后继节点一定不会有两个子节点
	 * @param data
	 */
	public void Tree_Delete(int data)
	{
		Node z = Tree_Search(data);
		Node x,y;
		if(z==null)return;     // 不存在元素data
		
	    if((z.getLeft()==null)||(z.getRight()==null)) //如果是前两种情况
	    {
	    	y = z;
	    }
	    else y = Tree_Successor(data);// 第三种情况
		
	    if(y.getLeft()!=null) // 获得要删除节点的子节点
	    	x = y.getLeft();
	    else x = y.getRight();
	    
	    if(x!=null)
	    	x.setParrent(y.getParrent());
	    if(y.getParrent()==null)
	    	boot = x;
	    else if(y==y.getParrent().getLeft())
	    	y.getParrent().setLeft(x);
	    else y.getParrent().setRight(x);
	    
	    if(y!=z)  //删除节点不是指定节点，那么是第三种情况
	    {
	    	z.setData(y.getData()); //修改删除节点的data 域为它的后继节点的data域 ，相对于写该引用简单很多
	    }
		
	}
}

MainClass ,调试的主类：

package SearchTree;

public class MainClass {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Tree T =new Tree();
		
		int[] a = {4 ,3 ,5,2,6,7,1};
		
		for(int i=0;i < a.length; i++)
		{
			T.Tree_Insert(new Node(null, null, null, a[i]));
		}
		
		T.InOrder_Tree_Walk();
		System.out.println("The minmum element is :" +T.Tree_Minmum().getData());
		System.out.println("The Maximum element is :" + T.Tree_Maximum().getData());
		System.out.println("The element 6's successor is:" + T.Tree_Successor(6).getData());
		System.out.println("The element 6's predecessor is:" + T.Tree_Predecessor(6).getData());
		T.Tree_Delete(5);
		T.InOrder_Tree_Walk();
	}
}

查询二叉树的兑现

相关推荐