2012/4/9----二叉查找树（二叉排序树）的各种操作 博客分类： 算法 算法java二叉查找树二叉排序树akon405

不知不觉都快5天没更新内容了，倒不是自己坚持不下来。一方面是因为二叉树这一块难度也比开始增大了，所以学习进度也就相对来说慢了一点。但更重要的是在学算法的同时也还有其他东西需要学习，在算法上面不能花太多时间。

今天写的是和二叉查找树相关的java代码，包括了二叉查找树的创建，中序遍历，查询（分为递归和非递归两种），查找最小节点，查找最大节点，插入节点，删除节点，查找节点的前驱，查找节点的后继，查找节点的父亲节点。差不多有10种操作吧。

在贴代码之前，先介绍一下什么是二叉查找树（来自百度百科）：

二叉排序树（Binary Sort Tree）又称二叉查找树。 它或者是一棵空树；或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树；

至于具体的操作我就不说了，在我代码里面都有详细的注释说明，运行结果我也会贴出来。

ps:代码比较多，如果发现问题还望留言指正。

 

/*
 * 二叉查找树的java实现，包涵构造二叉查找树和对二叉查找树的一系列操作
 * @version 1.0 2012/4/9
 * @author akon
 */
package com.akon405.www;

public class BSTree {
	BSTreeNode rootNode;//创建根节点
	//创建二叉查找树
	public void createBSTree(int[] A){
		rootNode=new BSTreeNode(A[0],null,null);//初始化根节点
		
		for(int i=1;i<A.length;i++){//逐个取出数组A中的元素用来构造二叉查找树
			BSTreeNode tmpNode=rootNode;
			while(true){
				if(tmpNode.data>=A[i]){//小于等于根节点
					if(tmpNode.left==null){//如果左孩子为空，这把当前数组元素插入到左孩子节点的位置
						tmpNode.left=new BSTreeNode(A[i],null,null);
						break;
					}
					tmpNode=tmpNode.left;//如果不为空的话，则把左孩子节点用来和当前数组元素作比较
				}else{//大于根节点
					if(tmpNode.right==null){//如果右孩子为空，这把当前数组元素插入到左孩子节点的位置
						tmpNode.right=new BSTreeNode(A[i],null,null);
						break;
					}
					tmpNode=tmpNode.right;//如果不为空的话，则把右孩子节点用来和当前数组元素作比较
				}
				}
			}
		
	}
	//中序遍历二叉查找树（中序遍历之后便可以排序成功）
	public void inOrderBSTree(BSTreeNode x){
		if(x!=null){
			inOrderBSTree(x.left);//先遍历左子树
			System.out.print(x.data+",");//打印中间节点
			inOrderBSTree(x.right);//最后遍历右子树
		}
	}
	//查询二叉排序树--递归算法
	public BSTreeNode searchBSTree1(BSTreeNode x,BSTreeNode k){
		if(x==null||k.data==x.data){
			return x;//返回查询到的节点
		}
		if(k.data<x.data){//如果k小于当前节点的数据域
			return searchBSTree1(x.left,k);//从左孩子节点继续遍历
		}else{//如果k大于当前节点的数据域
			return searchBSTree1(x.right,k);//从右孩子节点继续遍历
		}
	}
	//查询二叉排序树--非递归算法
	public BSTreeNode searchBSTree2(BSTreeNode x,BSTreeNode k){
		while(x!=null&&k.data!=x.data){
			if(x.data>k.data){
				x=x.left;//从左孩子节点继续遍历
			}else{
				x=x.right;//从右孩子节点继续遍历
			}
		}
		return x;
	}
	//查找二叉查找树的最小节点
	public BSTreeNode searchMinNode(BSTreeNode x){
		while(x.left!=null){
			x=x.left;
		}
		return x;
	}
	//查找二叉查找树的最大节点
	public BSTreeNode searchMaxNode(BSTreeNode x){
		while(x.right!=null){
			x=x.right;
		}
		return x;
	}
	//插入节点进入二叉查找树
	public void insert(BSTreeNode k){
		BSTreeNode r=rootNode;
		BSTreeNode p,q=null;
		p=r;
		while(p!=null){//while语句可以找到k节点所要插入的位置的父亲节点q
			q=p;
			if(p.data>k.data){
				p=p.left;
			}else{
				p=p.right;
			}
		}
		if(q==null){//二叉查找树为空树的情况下，直接插入到根节点，这里的q为已知的k的父亲节点
			r.data=k.data;
		}else if(q.data>k.data){//插入到父亲节点q的左边
			q.left=k;
		}else{//插入到父亲节点q的右边
			q.right=k;
		}
	}
	//删除二叉查找树中指定的节点
	public void delete(BSTreeNode k){//分三种情况删除
		if(k.left==null&&k.right==null){//第一种情况--没有子节点的情况下
			BSTreeNode p=parent(k);
			if(p.left==k){//其为父亲节点的左孩子
				p.left=null;
			}else if(p.right==k){//其为父亲节点的右孩子
				p.right=null;
			}
		}else if(k.left!=null&&k.right!=null){//第二种情况--有两个孩子节点的情况下
			BSTreeNode s=successor(k);//k的后继节点
			delete(s);
			k.data=s.data;
		}else{//第三种情况--只有一个孩子节点的情况下
			BSTreeNode p=parent(k);
			if(p.left==k){
				if(k.left!=null){
					p.left=k.left;
				}else{
					p.left=k.right;
				}
			}else if(p.right==k){
				if(k.left!=null){
					p.right=k.left;
				}else{
					p.right=k.right;
				}
			}
			
		}
	}
	//查找节点的前驱节点
	public BSTreeNode predecessor(BSTreeNode k){
		if(k.left!=null){
			return searchMaxNode(k.left);//左子树的最大值
		}
		BSTreeNode y=parent(k);
		while(y!=null&&k==y.left){//向上找到最近的一个节点，其父亲节点的右子树包涵了当前节点或者其父亲节点为空
			k=y;
			y=parent(y);
		}
		return y;
	}
	//查找节点的后继节点
	public BSTreeNode successor(BSTreeNode k){
		if(k.right!=null){
			return searchMinNode(k.right);//右子树的最小值
		}
		BSTreeNode y=parent(k);
		while(y!=null&&k==y.right){//向上找到最近的一个节点，其父亲节点的左子树包涵了当前节点或者其父亲节点为空
			k=y;
			y=parent(y);
		}
		return y;
	}
	//求出父亲节点，在定义节点类BSTreeNode的时候，没有申明父亲节点，所以这里专门用parent用来输出父亲节点（主要是不想修改代码了，就在这里加一个parent函数吧）
	public BSTreeNode parent(BSTreeNode k){
		BSTreeNode p=rootNode;
		BSTreeNode tmp=null;
		while(p!=null&&p.data!=k.data){//最后的p为p。data等于k.data的节点，tmp为p的父亲节点
			if(p.data>k.data){
				tmp=p;//临时存放父亲节点
				p=p.left;
			}else{
				tmp=p;//临时存放父亲节点
				p=p.right;
			}
		}
		return tmp;
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] A={23,12,43,2,87,54};
		BSTreeNode searchNode1=null;//递归查找到的结果
		BSTreeNode searchNode2=null;//非递归查找到的结果
		BSTreeNode searchMinNode=null;//最小节点
		BSTreeNode searchMaxNode=null;//最大节点
		BSTreeNode k=null,l=null,p=null,q=null,m=null,n=null;//申明6个节点k,l,p,q,m,n
		
		System.out.print("打印出数组A中的元素");
		for(int i=0;i<A.length;i++)
		System.out.print(A[i]+",");
		
		BSTree bs=new BSTree();
		
		bs.createBSTree(A);//创建二叉查找树
		
		System.out.println();
		System.out.print("中序遍历构造的二叉查找树：");
		bs.inOrderBSTree(bs.rootNode);//中序遍历二叉查找树
		
		k=new BSTreeNode(23,null,null);//初始化一节点k，其data为null，左右孩子为null
		l=new BSTreeNode(17,null,null);//初始化一节点l，其data为null，左右孩子为null
		q=new BSTreeNode(12,null,null);//初始化一节点q，其data为null，左右孩子为null
		m=bs.searchBSTree2(bs.rootNode, k);//从二叉查找树里面查找一个节点，其m.data为k.data(这个m节点在后面用来测试程序)
		searchNode1=bs.searchBSTree1(bs.rootNode,k);//查询二叉查找树----递归算法
		searchNode2=bs.searchBSTree2(bs.rootNode,k);//查询二叉查找树----递归算法
		
		System.out.println("");
		System.out.println("递归算法--查找节点域："+searchNode1.data+"左孩子："+searchNode1.left.data+"右孩子："+"查找节点域："+searchNode1.right.data);//这里的左孩子或者右孩子节点可能打印为空，会出现null异常
		System.out.println("非递归算法--查找节点域："+searchNode2.data+"左孩子："+searchNode2.left.data+"右孩子："+"查找节点域："+searchNode2.right.data);//这里的左孩子或者右孩子节点可能打印为空，会出现null异常
		
		searchMinNode=bs.searchMinNode(bs.rootNode);//找到最小节点
		searchMaxNode=bs.searchMaxNode(bs.rootNode);//找到最大节点
		
		System.out.println("最小节点："+searchMinNode.data);
		System.out.println("最大节点："+searchMaxNode.data);
		
		bs.insert(l);//把l节点插入到二叉查找树中
		
		System.out.print("插入l节点(l的data为17)之后的二叉查找树的中序遍历结果:");
		bs.inOrderBSTree(bs.rootNode);//中序遍历二叉查找树
				
		p=bs.parent(q);//取q节点的父亲节点
		
		System.out.println("");
		System.out.println("q的父亲节点(q的data为12)："+p.data+"左孩子："+p.left.data+"右孩子："+"查找节点域："+p.right.data);//这里的左孩子或者右孩子节点可能打印为空，会出现null异常
		
		bs.delete(l);
		System.out.print("删除l节点(l的data为17)之后的二叉查找树的中序遍历结果:");
		bs.inOrderBSTree(bs.rootNode);//中序遍历二叉查找树
		
		n=bs.successor(m);
		System.out.println("");
		System.out.println("K的后继节点(k的data为23)："+n.data);
		
		n=bs.predecessor(m);
		System.out.println("K的前驱节点(k的data为23)："+n.data);
	}

}

//二叉查找树的节点类
class BSTreeNode{
	int data;//数据域
	BSTreeNode right;//左孩子
	BSTreeNode left;//右孩子
	//构造二叉查找树的节点
	public  BSTreeNode(int data,BSTreeNode right,BSTreeNode left){
		this.data=data;
		this.right=right;
		this.left=left;
	}

}

 

运行结果如下：

 

打印出数组A中的元素23,12,43,2,87,54,
中序遍历构造的二叉查找树：2,12,23,43,54,87,
递归算法--查找节点域：23左孩子：12右孩子：查找节点域：43
非递归算法--查找节点域：23左孩子：12右孩子：查找节点域：43
最小节点：2
最大节点：87
插入l节点(l的data为17)之后的二叉查找树的中序遍历结果:2,12,17,23,43,54,87,
q的父亲节点(q的data为12)：23左孩子：12右孩子：查找节点域：43
删除l节点(l的data为17)之后的二叉查找树的中序遍历结果:2,12,23,43,54,87,
K的后继节点(k的data为23)：43
K的前驱节点(k的data为23)：12