文档章节

java实现二叉查找树

Choaya
 Choaya
发布于 2017/02/13 17:56
字数 1572
阅读 59
收藏 0

什么是二叉查找树?

前面写了一篇介绍二叉树的文章 https://my.oschina.net/u/1587638/blog/834842

二叉树的问题: 二叉树中的节点数据没有任何任何规律, 导致在二叉树中查找数据的时候效率比较低. 于是出现了二叉查找树. 那什么是二叉查找树呢? 用自己的话说: 二叉查找树是一种特殊的二叉树, 二叉查找树的每个节点都大于其左子树节点, 小于其右子树节点.

代码实现

二叉查找树节点

public class BSTNode<T> {
	T data;
	BSTNode<T> left;
	BSTNode<T> right;
	BSTNode<T> parent;

	public BSTNode(T data, BSTNode<T> left, BSTNode<T> right, BSTNode<T> parent) {
		this.data = data;
		this.left = left;
		this.right = right;
		this.parent = parent;
	}
}

这和前面介绍的二叉树一样, 不同的是树中数据的排序方式.

前序遍历

// 前序遍历
private void preOrder(BSTNode<T> node) {
	if (node != null) {
        System.out.print(node.data+" ");
    	preOrder(node.left);
        preOrder(node.right);
	}
}

public void preOrder() {
	preOrder(root);
}

中序遍历

// 中序遍历
private void inOrder(BSTNode<T> node) {
	if (node != null) {
		inOrder(node.left);
		System.out.print(node.data + " ");
		inOrder(node.right);
	}
}

public void inOrder() {
	inOrder(root);
}

后序遍历

// 后序遍历
private void postOrder(BSTNode<T> node) {
	if (node != null) {
		postOrder(node.left);
		postOrder(node.right);
		System.out.print(node.data + " ");
	}
}

public void postOrder() {
	postOrder(root);
}

到此为止, 与前面的二叉树都没有什么区别, 下面开始介绍二叉查找树.

查找

在一般的二叉树中, 我们想实现查找的话只能通过遍历树来实现, 但是这样的做的效率太低了, 由于二叉树满足一定的规律, 利用这个规律, 可以减少遍历的次数.

递归实现

// 查找
private BSTNode<T> contains(BSTNode<T> node, T data) {
	if (node == null) {
		return null;
	}
	int cmp = data.compareTo(node);
	if (cmp < 0) {
		return contains(node.left, data);
	} else if (cmp > 0) {
		return contains(node.right, data);
	} else {
		return node;
	}
}

public BSTNode<T> contains(T data) {
	return contains(root, data);
}

 非递归实现

// 非递归实现
private BSTNode<T> iterativeContains(BSTNode<T> node, T data) {
	while (node != null) {
		int cmp = data.compareTo(node.data)
		if (cmp < 0) {
			node = node.left;
		} else if (cmp > 0) {
			node = node.right;
		} else {
			return node;
		}
	}
	return node;
}

public BSTNode<T> iterativeContains(T data) {
	return iterativeContains(root, data);
}

查找最大值

// 最大值
private BSTNode<T> findMax(BSTNode<T> node) {
	if (node == null) {
		return null;
	}
	while (node.right != null) {
		node = node.right;
	}
	return node;
}

public T findMax() {
	BSTNode<T> node = findMax(root);
	if (node != null) {
		return node.data;
	}
	return null;
}

查找最小值

// 最小值
private BSTNode<T> findMin(BSTNode<T> node) {
	if (node == null) {
		return null;
	}
	while (node.left != null) {
		node = node.left;
	}
	return node;
}

public T findMin() {
	BSTNode<T> node = findMax(root);
	if (node != null) {
		return node.data;
	}
	return null;
}

前驱和后继

首先来解释一下什么是前驱, 什么是后继. 

首先将树中所有的节点按照从小到大排序, 某个节点的前驱就是排在它前面一个的节点, 后继就是排在它后面的节点.

在二叉查找树中, 节点的前驱就是该节点左子树的最大值; 节点的后继就是该节点右子树的最小值.

查找前驱

// 查找前驱
public BSTNode<T> predecessor(BSTNode<T> node) {
	// 如果节点为空
	if (node == null) {
		return null;
	}

	// 如果该节点有左子树, 那么前驱就是左子树的最大值
	if (node.left != null) {
		return findMax(node.left);
	}

	// 如果该节点没有左子树, 那么有2种情况
	// 1. 如果node是一个右孩子, 那么node的前驱是它的父节点
	// 2. 如果node是一个左孩子, 由二叉查找树的性质可以知道, 
	// 其前驱一定是其最近的父节点, 且node在这个前驱节点的右子树上(大家思考一下是不是这样的?)
	BSTNode<T> parent = node.parent;
	while((parent != null) && (node == parent.left)) {
		node = parnet;
		parent = parent.parent;
	}
	return parent;
}

查找后继

// 查找后继
public BSTNode<T> successor(BSTNode<T> node) {
	if (node == null) {
		return null;
	} 
	// 如果该节点有右子树, 那么后继就是右子树的最小值
	if (node.right != null) {
		findMin(node.right);
	}
	// 如果该节点没有右子树, 那么有2种情况:
	// 1. 如果node是一个左孩子, 那么后继就是node的父节点
	// 2. 如果node是一个右孩子, 由二叉查找树的性质可以知道
	// 其前驱一定是其最近的父节点, 且node在这个前驱节点的左子树上(大家思考一下是不是这样的?)
	BSTNode<T> parent = node.parent;
	while((parent != null) && parent.right == node) {
		node = parent;
		parent = parent.parent;
	}
	return parent;
}

插入

  1. 若当前的二叉查找树为空,则插入的元素为根节点 
  2. 若插入的元素值小于根节点值,则将元素插入到左子树中
  3. 若插入的元素值不小于根节点值,则将元素插入到右子树中。首先找到插入的位置,要么向左,要么向右,直到找到空结点,即为插入位置,如果找到了相同值的结点,插入失败。
// 插入
public void insert(T data) {
	// 新建节点
    BSTNode<T> node = new BSTNode<T>(data,null,null,null);
    if (node != null)
        root = insert(root, node);
}

/**
 * 递归版
 */
private BSTNode<T> insert(BSTNode<T> node, BSTNode<T> insert) {
	if (node == null) {
		node = insert;
	}
	int cmp = insert.data.compareTo(node.data);
	if (cmp < 0) {
		node.left = insert(node.left, insert);
		node.left.parent = node;
	} else if(cmp > 0) {
		node.right = insert(node.right, insert);
		node.right.parent = node;
	}
	return node;
}

// 非递归版
private void insert(BSTNode<T> node, BSTNode<T> insert) {
	if (root == null) {
		root = insert;
		return;
	}
	int cmp = 0;
	// 记录父节点
	BSTNode<T> p = null;
	while (node != null) {
		p = node;
		cmp = insert.data.compareTo(node.data);
		if (cmp < 0) {
			node = node.left;
		} else if (cmp > 0) {
			node = node.right;
		} else {
			return;
		}
	}
	insert.parent = p;
	if (cmp < 0) {
		p.left = insert;
	}else if (cmp > 0) {
		p.right = insert;
	}
}

删除

二叉查找树的删除,分三种情况进行处理:

  1. p为叶子节点,直接删除该节点,再修改其父节点的指针(注意分是根节点和不是根节点),如图a。
  2. p为单支节点(即只有左子树或右子树)。让p的子树与p的父亲节点相连,删除p即可;(注意分是根节点和不是根节点);如图b。
  3. 有两个孩子的情况,当前结点与左子树中最大的元素交换,然后删除当前结点。左子树最大的元素一定是叶子结点,交换后,当前结点即为叶子结点,删除参考没有孩子的情况。另一种方法是,当前结点与右子树中最小的元素交换,然后删除当前结点。如图c。

public void remove(T data) {
    remove(root, data);
}

// 递归实现
private BSTNode<T> remove(BSTNode<T> node, T data) {
	if (node == null) {
		return null;
	}
	int cmp = data.compareTo(node.data);
	if (cmp < 0) {
		node.left = remove(node.left, data);
	} else if (cmp > 0) {
		node.right = remove(node.right, data);
	} else if (node.left != null && node.right != null) {
			node.data = findMin(node.right).data;
			node.right = remove(node.right, node.data);
	} else {
		BSTNode<T> p = node.parent;
		if (node.left != null) {
			node = node.left;
		} else {
			node = node.right;
		}
		node.parent = p;
	}
	return node;
}

 

© 著作权归作者所有

下一篇: maven插件
Choaya
粉丝 3
博文 7
码字总数 2953
作品 0
成都
程序员
私信 提问
《数据结构与算法系列》合集整理

《数据结构与算法系列》合集整理 整理来自博客园skywang12345,以下摘自作者介绍: “最近抽空整理了"数据结构和算法"的相关文章。在整理过程中,对于每种数据结构和算法分别给出"C"、"C++"...

kaixin_code
2018/12/01
188
0
数据结构笔记--二叉查找树概述以及java代码实现

一些概念:   二叉查找树的重要性质:对于树中的每一个节点X,它的左子树任一节点的值均小于X,右子树上任意节点的值均大于X.   二叉查找树是java的TreeSet和TreeMap类实现的基础.   由于树...

冬至饮雪
2016/05/14
0
0
一文掌握关于Java数据结构所有知识点(欢迎一起完善)

在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系...

snailclimb
2018/05/08
0
0
数据结构知识学习与面试 一点课堂(多岸学院)

Queue 什么是队列 队列是数据结构中比较重要的一种类型,它支持 FIFO,尾部添加、头部删除(先进队列的元素先出队列),跟我们生活中的排队类似。 队列的种类 单队列(单队列就是常见的队列,...

程伟鑫
09/11
22
0
学习数据结构 二叉查找树(binary search tree)

为学习 LLVM 的 ImmutableSet,其底层的实现选择为 AVL 树(平衡二叉搜索树),我不很熟悉该树,虽然大致知道但毕竟不精,因此还是先学习学习二叉搜索树吧。 二叉搜索树或叫做二叉查找树,可...

刘军兴
2012/03/16
311
2

没有更多内容

加载失败,请刷新页面

加载更多

006-Sigle-基于blockstack去中心化博客

本篇文章主要讲解有关基于Blockstack的Sigle是一个去中心化的博客项目; 官网地址:https://www.sigle.io/ Github地址:https://github.com/pradel/sigle 页面展示: 介绍: A beautiful de...

Riverzhou
24分钟前
9
0
驰骋工作流引擎开发平台属性功能的隐藏显示介绍

关键字: 工作流程管理系统 工作流引擎 asp.net工作流引擎 java工作流引擎. 表单引擎 工作流功能说明 工作流设计 工作流快速开发平台 业务流程管理 bpm工作流系统 java工作流主流框架 自定义...

孟娟
25分钟前
8
0
MyBatis binding 模块分析

MyBatis binding 模块分析 binding功能代码所在包 org.apache.ibatis.binding binding模块作用 封装ibatis编程模型 ibatis编程模型中,SqlSession作为sql执行的入口,实用方法为sqlSession.se...

红妍落日
27分钟前
7
0
网易互娱的数据库选型和 TiDB 应用实践

作者介绍:李文杰,网易互娱计费组,高级数据库管理工程师,TiDB User Group Ambassador。 一、业务架构简介 计费组是为网易互娱产品提供统一登录和支付高效解决方案的公共支持部门,对内是互...

TiDB
34分钟前
10
0
Debezium接入Mysql遇到到的Tinyint坑

问题背景: 在Debezium做数据初始化的时候,对于一些tinyint字段的值,出现0,1的值的异常。 经过源码排查,数据在JDBC上面,读取到的数据是Boolean值。 通过排查,原来是MYSQL特有的数据问题...

吐槽的达达仔
42分钟前
11
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部