二叉查找树(排序树)与java实现

以你之姓@ 2022-09-30 12:54 152阅读 0赞

**二叉查找树(排序树)与java实现**

**一.二叉查找树的基本特点**

**二.java实现**

**三.二叉查找树增删改查时间复杂度**

**一.二叉查找树基本特点**

1.1 若任意节点的左子树不空，则左子树上所有节点的值均小于等于它的根节点的值；

1.2 若任意节点的右子树不空，则右子树上所有节点的值均大于等于它的根节点的值；

1.3 任意节点的左、右子树也分别为二叉查找树。

**二.二叉查找树的java实现**

package comUtils;
    
    /**@description
     * 二叉查找树(排序树)基本类
     * @author Jintao_Ma
     */
    public class BSTree<T extends Comparable<T>>{
    	/*基本方法*/
    	private boolean isNull(BSNode<T> bSNode){
    		return null == bSNode;
    	}
    	
    	private boolean isNotNull(BSNode<T> bSNode){
    		return !isNull(bSNode);
    	}
    	
    	BSNode<T> root; /*根节点*/
    	
    	public class BSNode<S extends Comparable<T>>{
    		S key; /*当前节点的值*/
    		BSNode<S> parent; /*父节点,设置该属性是为了更方便的查找上级*/
    		BSNode<S> left; /*左孩子*/
    		BSNode<S> right; /*右孩子*/
    		
    		public BSNode(S key, BSNode<S> parent, BSNode<S> left, BSNode<S> right) {
    			super();
    			this.key = key;
    			this.parent = parent;
    			this.left = left;
    			this.right = right;
    		}
    	}
    
    	/**@description 
    	 * 初始化二叉树
    	 */
    	public BSTree(){
    	}
    	
    	/**@description
    	 * 判断树是否为空
    	 */
    	public boolean isEmpty(){
    		return isNull(root);
    	}
    	
    	/**@description
    	 * 初始化二叉树
    	 */
    	public void init(){
    		root = null;
    	}
    	
    	/**@description
    	 * 判断节点是不是根节点
    	 */
    	public boolean isRoot(BSNode<T> bSNode){
    		return (root == bSNode)? true:false;
    	}
    	
    	/**@description 
    	 * 添加节点
    	 */
    	public boolean addBSNode(T key){
    		/*判断添加节点是否成功*/
    		boolean result = true;
    		BSNode<T> bSNode = new BSNode<T>(key, null, null, null);
    		if(isEmpty()){
    			root = bSNode;
    		}else{
    			result =  insert(root,bSNode);
    		}
    		return result;
    	}
    	private boolean insert(BSNode<T> root,BSNode<T> bSNode){
    		/*判断添加节点是否成功*/
    		boolean result = true;
    		if(bSNode.key.compareTo(root.key) < 0){
    			if(isNotNull(root.left)){
    				result = insert(root.left,bSNode);
    			}else{
    				root.left = bSNode;
    				bSNode.parent = root;
    			}
    		}else if(bSNode.key.compareTo(root.key) > 0){
    			if(isNotNull(root.right)){
    				result = insert(root.right,bSNode);
    			}else{
    				root.right = bSNode;
    				bSNode.parent = root;
    			}
    		}else{
    			result = false;/*值相等什么也不做*/
    		}
    		return result;
    	}
    	
    	/**@description 
    	 * 删除节点,如果不破坏树的结构(中序遍历是递增的)，那么分三种情况：
    	 * 1)需要删除的节点下并没有其他子节点
    	 * 2)需要删除的节点下有一个子节点(左或者右)
    	 * 3)需要删除的节点下有两个子节点(通过查找它的前驱节点(后继节点)，然后替换该节点，最后删除前驱节点(后继节点)),然后执行步骤2)
    	 */
    	public boolean delBSNode(T key){
    		boolean del = false;
    		BSNode<T> BSNode = findAllNode(key);
    		if(isNull(BSNode)){
    			return del;
    		}else{
    		}
    		/**该节点无任何子节点*/
    		if(isNull(BSNode.left) && isNull(BSNode.right)){
    			if(!isRoot(BSNode)){  /*非根节点*/
    				if(BSNode==BSNode.parent.left){ /*如果是父节点的左孩子*/
    					BSNode.parent.left = null;  /*删除父节点的左引用*/
    				}else{
    					BSNode.parent.right = null; /*删除父节点的右引用*/
    				}
    			}else{ /*根节点*/
    				init();
    			}
    			del = true;
    		/**该节点只有一个子节点*/
    		}else if(isNull(BSNode.left) || isNull(BSNode.right)){
    			if(!isRoot(BSNode)){ /*非根节点*/
    				if(isNull(BSNode.left)){ /*该节点只有一个右孩子*/
    					if(BSNode==BSNode.parent.left){ /*如果是父节点的左孩子*/
    						BSNode.parent.left = BSNode.right; /*父节点的左引用指向该节点的右孩子*/
    					}else{
    						BSNode.parent.right = BSNode.right; /*父节点的右引用指向该节点的右孩子*/
    					}
    					BSNode.right.parent = BSNode.parent; /*修改右孩子的父引用*/ 
    				}else{ /*该节点只有一个左孩子*/
    					if(BSNode==BSNode.parent.left){ /*如果是父节点的左孩子*/
    						BSNode.parent.left = BSNode.left; /*父节点的左引用指向该节点的左孩子*/
    					}else{
    						BSNode.parent.right = BSNode.left; /*父节点的右引用指向该节点的左孩子*/
    					}
    					BSNode.left.parent = BSNode.parent; /*修改左孩子的父引用*/ 
    				}
    			}else{ /*根节点*/
    				if(isNull(BSNode.left)){
    					BSNode.right.parent = null;
    					root = BSNode.right;
    				}else{
    					BSNode.left.parent = null;
    					root = BSNode.left;
    				}
    			}
    			del = true;
    		/**两个子节点*/
    		}else{
    			BSNode<T> preNode = MaxBode(BSNode.left);/*先查找该节点的前驱节点(后继节点)*/
    			SwitchKey(preNode,BSNode);/*交换两个BSNode的值*/
    			del = delBSNode(preNode.key);
    		}
    		return del;
    	}
    
    	/**@description
    	 * 交换两个Node的值
    	 */
    	public void SwitchKey(BSNode<T> A,BSNode<T> B){
    		T key;
    		key = A.key;
    		A.key = B.key;
    		B.key = key;
    	}
    	
    	/**@description
    	 * 返回key所在的节点(中序查找所有节点)
    	 */
    	public BSNode<T> findAllNode(T key){
    		return isNull(root)? null:middleFindByKey(root,key);
    	}
    	
    	public BSNode<T> middleFindByKey(BSNode<T> treeNode,T key){
    		BSNode<T> bSNode = null;
    		/*优先查找左自树*/
    		if(isNotNull(treeNode.left)){
    			bSNode = middleFindByKey(treeNode.left,key);
    			if(isNotNull(bSNode)){
    				return bSNode;
    			}
    		}else{
    		}
    		/*查找中间节点*/
    		if(0 == treeNode.key.compareTo(key)){
    			return bSNode = treeNode;
    		}else{
    		}
    		/*查找右子树*/
    		if(isNotNull(treeNode.right)){
    			bSNode = middleFindByKey(treeNode.right,key);
    			if(isNotNull(bSNode)){
    				return bSNode;
    			} 
    		}else{
    		}
    		return bSNode;
    	}
    	
    	public BSNode<T> middleFindByKey(T key){
    		return middleFindByKey(root,key);
    	}
    	
    	/**@description
    	 * 查找树(子树)中的最大节点  即后继节点
    	 * @return
    	 * BSNode<T>
    	 */
    	public BSNode<T> MaxBode(BSNode<T> tree){
    		if(isNotNull(tree)){
    			if(isNotNull(tree.right)){
    				return MaxBode(tree.right);
    			}else{
    				return tree;
    			}
    		}else{
    			return null;
    		}
    	}
    	
    	/**@description
    	 * 查找树(子树)中的最小节点  即前驱节点
    	 * @return
    	 * BSNode<T>
    	 */
    	public BSNode<T> MinBode(BSNode<T> tree){
    		if(isNotNull(tree)){
    			if(isNotNull(tree.left)){
    				return MinBode(tree.left);
    			}else{
    				return tree;
    			}
    		}else{
    			return null;
    		}
    	}
    	
    	/**@description 
    	 * 前序遍历
    	 */
    	public void beforeFind(BSNode<T> treeNode){
    		if(isNotNull(treeNode)){
    			System.out.println(treeNode.key);
    			beforeFind(treeNode.left);
    			beforeFind(treeNode.right);
    		}else{
    		}
    	}
    	public void beforeFind(){
    		beforeFind(root);
    	}
    	
    	/**@description 
    	 * 中序遍历
    	 */
    	public void middleFind(BSNode<T> treeNode){
    		if(isNotNull(treeNode)){
    			middleFind(treeNode.left);
    			System.out.println(treeNode.key);
    			middleFind(treeNode.right);
    		}else{
    		}
    	}
    	public void middleFind(){
    		middleFind(root);
    	}
    	
    	/**@description 
    	 * 后序遍历
    	 */
    	public void afterFind(BSNode<T> treeNode){
    		if(isNotNull(treeNode)){
    			afterFind(treeNode.left);
    			afterFind(treeNode.right);
    			System.out.println(treeNode.key);
    		}else{
    		}
    	}
    	public void afterFind(){
    		afterFind(root);
    	}
    	
    	/*测试函数*/
    	public static void main(String[] args) {
    		BSTree<Integer> bSTree = new BSTree<Integer>();
    		bSTree.addBSNode(new Integer(2));
    		bSTree.addBSNode(new Integer(1));
    		bSTree.addBSNode(new Integer(4));
    		bSTree.addBSNode(new Integer(3));
    		bSTree.addBSNode(new Integer(5));
    		bSTree.addBSNode(new Integer(6));
    		bSTree.addBSNode(new Integer(9));
    		bSTree.addBSNode(new Integer(7));
    		bSTree.addBSNode(new Integer(8));
    //		bSTree.delBSNode(new Integer(2));
    		
    //		bSTree.beforeFind();/*先序遍历*/
    		bSTree.middleFind();/*中序遍历*/ 
    //		bSTree.afterFind();/*后序遍历*/
    	}
    }

关于删除的详细算法可参照此文:[http://blog.csdn.net/wangyunyun00/article/details/23708055][http_blog.csdn.net_wangyunyun00_article_details_23708055]

**三.二叉查找树增删改查时间复杂度**

3.1 二叉树的所有操作均基于查找: 如果树趋于饱和的话，查找基本等同于折半查找，设所有节点总数N，则查找次数为为时间复杂度为Log2(N+1)（即树的高度）,那么时间复杂度就是LogN；

3.2 修改基于查找，复杂度也是LogN

3.3 新增意味着添加新的叶子节点，只需要查到到合适的添加位置，复杂度也是LogN

3.4 删除的话，如果删除的是节点是叶子节点或者只有一个子树，那么直接删除即可。如果删除的结点有左右子树，那么找到节点后，还需要先查找其前驱或者后继节点，不过这部影响复杂度，复杂度仍为LogN

3.5 另外需要注意的是，实际情况下，二叉查找树并不一定是一颗满树，甚至有可能是一颗线性树(节点数就是树的高度)，那么复杂度就是N;综上，二叉查找树的时间复杂度介于LogN和N之间

[http_blog.csdn.net_wangyunyun00_article_details_23708055]: http://blog.csdn.net/wangyunyun00/article/details/23708055