欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-25 09:57:34
...

不知不觉都快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