Java实现数据结构之二叉查找树

一、综述

二叉查找树或者是一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的节点。

基于二叉查找树树的二叉查找算法具有很高的效率O（logn)，是一种很适合查找的数据结构，但是它也有确定，比如不够平衡。因此有改进后的平衡二叉查找树（AVL），这个下一篇再讲。

二、Java实现二叉查找树

/**
 * @author 王勤为 
 * 
 * 这是实现二叉查找树的类
 * 
 * 主要实现二叉排序树的建立、插入元素、删除元素、查找元素
 */
public class ABinarySortTree {

	//内部类：节点对象
	public class Node {

		Node(int value) {
			this.value = value;
		}
		int value;
		Node parent=null;
		Node leftChild = null;
		Node rightChild = null;
	}
	
	public Node root; // 树的根节点

	//建树方法一：根据一个值建树
	ABinarySortTree(int r) {
		this.root = new Node(r);
	}

	//建树方法二：根据一个数组建树  实质就是不停的调用插入方法
    ABinarySortTree(int[] array) {
    	this.root=null;
		for(int e:array){
			this.insert(this, e);
		}
		}
	//建树方法三：根据一个节点建树
	ABinarySortTree(Node r) {
		this.root = r;
	}
	
	/**插入一个节点
	 * @param root   插入树的根节点
	 * @param temp_value 值
	 */
	public void insert(ABinarySortTree tree,int temp_value){
		//先把值变成节点对象
		Node newNode=new Node(temp_value);
		Node root=tree.root;
		
		if(root==null){//如果树空，则此节点直接成为根节点
			tree.root=newNode;
			System.out.println("插入根元素："+newNode.value);
			return;
		}
		
		if(root.value==temp_value){//如果根节点值和插入值相等，说明不需要插入
			System.out.println("树中已经存在"+temp_value+"不需要插入");
			return;
		}
		
		if(root.leftChild==null&&temp_value
   
    root.value){//如果根节点没有右孩子且插入值大于根节点值
			newNode.parent=root;
			root.rightChild=newNode;
			System.out.println("插入"+root.value+"的右孩子元素："+root.rightChild.value);
			return;
		}
		
		if(temp_value
    
     root.value){//如果根节点有右孩子且插入值大于根节点值
			//递归调用
			insert(new ABinarySortTree(root.rightChild),temp_value);
		}
		
	}
	
	/**查找算法，原理跟插入算法类似
	 * @param root
	 * @param temp_value
	 * @return  有返回值证明查找成功
	 */
	public Node search(Node root,int temp_value){
		
		if (root == null) {// 如果树空
			System.out.println("树空！");
			return null;
		}
		if (root.value == temp_value) {// 如果根节点值和插入值相等，返回根节点
			return root;
		}
		if (root.leftChild != null && temp_value < root.value) {// 如果根节点有左孩子且插入值小于根节点值
			// 递归调用
			return search(root.leftChild, temp_value);
		}
		if (root.rightChild != null && temp_value > root.value) {// 如果根节点有右孩子且插入值大于根节点值
			// 递归调用
			return search(root.rightChild, temp_value);
		}
		return null;// 其他情况都返回空
		
	}
	
	
	/**查找树中最小的元素
	 * @return
	 */
	public Node searchMin(Node root){
		if(root==null) return null;
		
		if (root.leftChild != null) {// 如果根节点有左孩子
			// 递归调用
			return searchMin(root.leftChild);
		}
		if (root.leftChild == null ) {// 如果根节点没有左孩子
			
			return root;
		}
		return null;
	}
	
	/**查找树中最大的元素
	 * @return
	 */
	public Node searchMax(Node root){
		if(root==null) return null;
		
		if (root.rightChild != null) {// 如果根节点有右孩子
			// 递归调用
			return searchMax(root.rightChild);
		}
		if (root.rightChild == null ) {// 如果根节点没有右孩子
			
			return root;
		}
		return null;
	}
	
	
	
	/**根据值删除节点
	 * @param temp_value
	 */
	public void delete(ABinarySortTree tree,int temp_value){
		//先找到该值对应的节点
		Node n=search(tree.root,temp_value);
		
		if(n==null) return;  //不存在则返回
		
		//如果该节点是叶子节点，直接删除
		if(n.leftChild==null&n.rightChild==null){
		    replace(n, null);
		}
		// 如果该节点有两个孩子,用其右子树中最小的数据代替要删除的结点数据，并递归删除该结点
		else if (n.leftChild != null & n.rightChild != null) {
			Node parent = n.parent;
			Node rightMin=searchMin(n.rightChild); //找到右子树中最小节点
			
			//递归删除该节点
			delete(tree,rightMin.value);
			
			if (parent.leftChild!=null&&parent.leftChild.equals(n)) {// n属于左子树
				parent.leftChild =rightMin;
			}
			if (parent.rightChild!=null&&parent.rightChild.equals(n)) {// n属于右子树
				parent.rightChild =rightMin;
			}
			rightMin.parent=parent;
			rightMin.leftChild=n.leftChild;
			rightMin.rightChild=n.rightChild;
		}
		
		//如果该节点只有一个孩子,直接用该孩子代替它的位置
		else if(n.leftChild!=null|n.rightChild!=null){
			if (n.leftChild != null) {
				replace(n,n.leftChild);
			}
			if (n.rightChild != null) {
				replace(n,n.rightChild);
			} 
		}
		
	}
	
	
	/**在树中，用新的节点树代替老节点
	 * @param origin 老节点
	 * @param fresh 新节点 可以传入空值,这时候是删除原节点
	 */
	public void replace(Node origin,Node fresh){
		
		Node parent = origin.parent; //获得老节点的父亲
		
		if (parent.leftChild!=null&&parent.leftChild.equals(origin)) {// origin属于左子树
				parent.leftChild = fresh;
				
			} 
		if (parent.rightChild!=null&&parent.rightChild.equals(origin)) {//origin属于右子树
			parent.rightChild = fresh;
		}
		if (fresh != null) {
			fresh.parent = parent;
		}
		
	}
	
	
	/**打印树的方法—— 中序遍历
	 * @param root
	 */
	public void printTreeByMiddle(Node root) {
		if (root == null) {
			return;
		}
		printTreeByMiddle(root.leftChild);
		System.out.print(root.value + " ");
		printTreeByMiddle(root.rightChild);
	}
	
	
	/**打印树的方法—— 前序遍历
	 * @param root
	 */
	public void printTreeByFront(Node root) {
		if (root == null) {
			return;
		}
		System.out.print(root.value + " ");
		printTreeByFront(root.leftChild);
		printTreeByFront(root.rightChild);
	}
}

三、调用检验

public class maintest {

	public static void main(String[] args) {

		int[] a = { 45, 6, 43, 78, 12, 90, 6,23, 21, 41, 64, 31, 91,91, 81, 6,4,7 };

		ABinarySortTree m= new ABinarySortTree(a);

		
		System.out.print("\n\n该树的中序遍历为：");
		m.printTreeByMiddle(m.root);
		System.out.print("\n该树的前序遍历为：");
		m.printTreeByFront(m.root);
		
		System.out.println("\n\n查找的元素为："+m.search(m.root, 90));
		
		System.out.println("\n删除元素元素：23");
		m.delete(m,23);
		
		System.out.print("删除后，该树的中序遍历为：");
		m.printTreeByMiddle(m.root);
		System.out.print("\n删除后，该树的前序遍历为：");
		m.printTreeByFront(m.root);
		
		System.out.println("\n\n插入元素元素：114");
		m.insert(m, 114);
		System.out.print("插入后，该树的中序遍历为：");
		m.printTreeByMiddle(m.root);
		System.out.print("\n插入后，该树的前序遍历为：");
		m.printTreeByFront(m.root);
		
		
		System.out.println("\n\n查找树中最小元素为："+m.searchMin(m.root).value);
		System.out.println("查找树中最大元素为："+m.searchMax(m.root).value);
	}
}

三、结果输出

插入根元素：45
插入45的左孩子元素：6
插入6的右孩子元素：43
插入45的右孩子元素：78
插入43的左孩子元素：12
插入78的右孩子元素：90
树中已经存在6不需要插入
插入12的右孩子元素：23
插入23的左孩子元素：21
插入23的右孩子元素：41
插入78的左孩子元素：64
插入41的左孩子元素：31
插入90的右孩子元素：91
树中已经存在91不需要插入
插入90的左孩子元素：81
树中已经存在6不需要插入
插入6的左孩子元素：4
插入12的左孩子元素：7


该树的中序遍历为：4 6 7 12 21 23 31 41 43 45 64 78 81 90 91 
该树的前序遍历为：45 6 4 43 12 7 23 21 41 31 78 64 90 81 91 

查找的元素为：[email protected]

删除元素元素：23
删除后，该树的中序遍历为：4 6 7 12 21 31 41 43 45 64 78 81 90 91 
删除后，该树的前序遍历为：45 6 4 43 12 7 31 21 41 78 64 90 81 91 

插入元素元素：114
插入91的右孩子元素：114
插入后，该树的中序遍历为：4 6 7 12 21 31 41 43 45 64 78 81 90 91 114 
插入后，该树的前序遍历为：45 6 4 43 12 7 31 21 41 78 64 90 81 91 114 

查找树中最小元素为：4
查找树中最大元素为：114

Java实现数据结构之二叉查找树

继续阅读

nginx location中斜线的位置的重要性

数据结构与算法（27）——排序（二）

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的简单使用

neo4j之cypher使用文档

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

mybatis_入门程序Mybatis入门

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

Effective Java 8:通用程序设计

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

Linux设备模型（中）之上层容器

scala (3) Function 和 Method