利用java实现二叉搜索树

二叉搜索树的定义

  • 它是一颗二叉树
  • 任一节点的左子树上的所有节点的值一定小于该节点的值
  • 任一节点的右子树上的所有节点的值一定大于该节点的值

特点: 二叉搜索树的中序遍历结果是有序的(升序)!

实现一颗二叉搜索树

  • 实现二叉搜索树,将实现插入,删除,查找三个方面
  • 二叉搜索树的节点是不可以进行修改的,如果修改,则可能会导致搜索树的错误

二叉搜索树的定义类

  • 二叉搜索树的节点类 —— class Node
  • 二叉搜索树的属性:要找到一颗二叉搜索树只需要知道这颗树的根节点。
public class BST {
    static class Node {
        private int key;
        private Node left;
        private Node right;

        public Node(int key) {
            this.key = key;
        }
    }

    private Node root;//BST的根节点
}

二叉搜索树的查找

  • 二叉搜索树的查找思路:
  • ①如果要查找的值等于当前节点的值,那么,就找到了
  • ②如果要查找的值小于当前节点的值,那么,就往当前节点的左子树走
  • ③如果要查找的值大于当前节点的值,那么,就往当前节点的右子树走
  • 最终,如果走到空了还没有找到,就说明不存在这个key
/**
 * 查找是否存在节点
 *
 * 思路:根据二叉排序树的特点:
 * ①如果要查找的值小于当前节点的值,那么,就往当前节点的左子树走
 * ②如果要查找的值大于当前节点的值,那么,就往当前节点的右子树走
 *
 * @param key 带查找的key
 * @return boolean是否存在
 */
public boolean find(int key) {
	Node cur = root;
	while (cur != null) {
		if (key < root.key) {
			cur = cur.left;
		} else if (key > root.key) {
			cur = cur.right;
		} else {
			return true;
		}
	}
	return false;
}

二叉搜索树的插入

  • 二叉搜索树的插入思路:
  • 思路和查找一样的,只是我们这次要进行的是插入操作,那么我们还需要一个parent节点,来时刻记录当前节点的双亲节点即:
  • ①如果要插入的值等于当前节点的值,那么,无法插入(不可出现重复的key
  • ②如果要插入的值小于当前节点的值,那么,就往当前节点的左子树走
  • ③如果要插入的值大于当前节点的值,那么,就往当前节点的右子树走
  • 最终,如果走到空了,就说明不存在重复的key,只要往双亲节点的后面插就好了,就是合适的位置,具体往左边还是右边插入,需要比较待插入节点的keyparentkey
/**
 * 往二叉树中插入节点
 *
 * 思路如下:
 *
 * @param key 待插入的节点
 */
public void insert(int key) {
	if (root == null) { //如果是空树,那么,直接插入
		root = new Node(key);
		return;
	}

	Node cur = root;
	Node parent = null; //parent 为cur的父节点
	while (true) {
		if (cur == null) { //在遍历过程中,找到了合适是位置,就指针插入(没有重复节点)
			if (parent.key < key) {
				parent.right = new Node(key);
			} else {
				parent.left = new Node(key);
			}
			return;
		}

		if (key < cur.key) {
			parent = cur;
			cur = cur.left;
		} else if (key > cur.key) {
			parent = cur;
			cur = cur.right;
		} else {
			throw new RuntimeException("插入失败,已经存在key");
		}
	}
}

二叉搜索树的删除

  • 二叉搜索树的删除思路:(详细的思路看注释
  • 首先,需要先找到是否存在key节点,如果存在,则删除,如果不存在则删除错误
  • 对于,如果存在,则分为三种情况:
  • ①要删除的节点,没有左孩子

Ⅰ:要删除的节点为根节点:root = delete.right;
Ⅱ:要删除的节点为其双亲节点的左孩子:parent.left = delete.right;
Ⅲ:要删除的节点为其双亲节点的右孩子:parent.right = delete.right;

  • ②要删除的节点,没有右孩子

Ⅰ:要删除的节点为根节点:root = delete.left;
Ⅱ:要删除的节点为其双亲节点的左孩子:parent.left = delete.left;
Ⅲ:要删除的节点为其双亲节点的右孩子:parent.right = delete.left;

  • ③要删除的节点,既有左孩子又有右孩子:

此时我们需要找到整颗二叉树中第一个大于待删除节点的节点,然后替换他俩的值,最后,把找到的节点删除
Ⅰ:找到的节点的双亲节点为待删除的节点:delete.key = find.key; findParent.right = find.right;
Ⅱ:找到的节点的双亲节点不是待删除的节点:delete.key = find.key; findParent.left = find.right;

/**
 * 删除树中节点
 *
 * 思路如下:
 *
 * @param key 待删除的节点
 */
public void remove(int key) {
	if (root == null) {
		throw new RuntimeException("为空树,删除错误!");
	}
	Node cur = root;
	Node parent = null;
	//查找是否key节点的位置
	while (cur != null) {
		if (key < cur.key) {
			parent = cur;
			cur = cur.left;
		} else if (key > cur.key) {
			parent = cur;
			cur = cur.right;
		} else {
			break;
		}
	}
	if (cur == null) {
		throw new RuntimeException("找不到key,输入key不合法");
	}

	//cur 为待删除的节点
	//parent 为待删除的节点的父节点
	/*
         * 情况1:如果待删除的节点没有左孩子
         * 其中
         * ①待删除的节点有右孩子
         * ②待删除的节点没有右孩子
         * 两种情况可以合并
         */
	if (cur.left == null) {
		if (cur == root) { //①如果要删除的是根节点
			root = cur.right;
		} else if (cur == parent.left) { //②如果要删除的是其父节点的左孩子
			parent.left = cur.right;
		} else { //③如果要删除的节点为其父节点的右孩子
			parent.right = cur.right;
		}
	}
	/*
         * 情况2:如果待删除的节点没有右孩子
         *
         * 其中:待删除的节点必定存在左孩子
         */
	else if (cur.right == null) { //①如果要删除的是根节点
		if (cur == root) {
			root = cur.left;
		} else if (cur == parent.left) { //②如果要删除的是其父节点的左孩子
			parent.left = cur.left;
		} else { //③如果要删除的节点为其父节点的右孩子
			parent.right = cur.left;
		}
	}
	/*
        * 情况3:如果待删除的节点既有左孩子又有右孩子
        *
        * 思路:
        * 因为是排序二叉树,要找到整颗二叉树第一个大于该节点的节点,只需要,先向右走一步,然后一路往最左走就可以找到了
        * 因此:
        * ①先向右走一步
        * ②不断向左走
        * ③找到第一个大于待删除的节点的节点,将该节点的值,替换到待删除的节点
        * ④删除找到的这个节点
        * ⑤完成删除
        *
         */
	else {
		Node nextParent = cur; //定义父节点,初始化就是待删除的节点
		Node next = cur.right; //定义next为当前走到的节点,最终目的是找到第一个大于待删除的节点
		while (next.left != null) {
			nextParent = next;
			next = next.left;
		}
		cur.key = next.key; //找到之后,完成值的替换
		if (nextParent == cur) { //此时的父节点就是待删除的节点,那么说明找到的节点为父节点的右孩子(因为此时next只走了一步)
			nextParent.right = next.right;
		} else { //此时父节点不是待删除的节点,即next确实往左走了,且走到了头.
			nextParent.left = next.right;
		}
	}

}

到此这篇关于利用java实现二叉搜索树的文章就介绍到这了,更多相关java二叉搜索树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java删除二叉搜索树最大元素和最小元素的方法详解

    本文实例讲述了Java删除二叉搜索树最大元素和最小元素的方法.分享给大家供大家参考,具体如下: 在前面一篇<Java二叉搜索树遍历操作>中完成了树的遍历,这一节中将对如何从二叉搜索树中删除最大元素和最小元素做介绍: 我们要想删除二分搜索树的最小值和最大值,就需要先找到二分搜索树的最小值和最大值,其实也还是很容易的,因为根据二叉搜索树的特点,它的左子树一定比当前节点要小,所以二叉搜索树的最小值一定是左子树一直往下走,一直走到底.同样在二叉搜索树中,右子树节点值,一定比当前节点要大,所以右子树一直

  • JAVA二叉树的几种遍历(递归,非递归)实现

    首先二叉树是树形结构的一种特殊类型,它符合树形结构的所有特点.本篇博客会针对二叉树来介绍一些树的基本概念,二叉树的基本操作(存储,返回树的深度,节点个数,每一层的节点个数),二叉树的四种遍历(层次,先序,中序,后序) 一.基本概念 二叉树有5种基本形态: 注:二叉树有序树,就是说一个节点的左右节点是有大小之分的,我们通常设定为左孩子一定大于右孩子,下面的实现都是基于这个规则的.二叉树分为三种:满二叉树,完全二叉树,不完全二叉树 二叉树的四种遍历:层次,先序,中序,后序首先是非递归实现上图的满二叉

  • java实现递归菜单树

    本文实例为大家分享了java实现递归菜单树的具体代码,供大家参考,具体内容如下 1.表结构 SET FOREIGN_KEY_CHECKS=0; -- ---------------------------- -- Table structure for menu -- ---------------------------- DROP TABLE IF EXISTS `menu`; CREATE TABLE `menu` ( `id` int(11) NOT NULL AUTO_INCREMEN

  • JAVA后台转换成树结构数据返回给前端的实现方法

    我们会经常用到树形,那么树形结构的数据是在前端做还是在后台做呢?我自己用过前端的ztree,selectTree等这些属于前端的组件,后台只需要把一个表的所有数据返回给前段就可以,前端可以通过id,pid来把层级结构划分,要是我们前端需要后台直接返回树结构数据怎么办,那么接下来我给大家介绍一下我写过的例子. 我们先看一张图了解一下树结构:我这里随便找一张图了解一下即可 接下来我们看一下数据,主要包括id,pid,名称 接下来我们写一个小例子,用递归方式转换为数 实体: package cn.cc

  • java哈夫曼树实例代码

    本文实例为大家分享了哈夫曼树java代码,供大家参考,具体内容如下 package boom; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Queue; class Node<T> implements Comparable<Node<T>>{ private T

  • java利用递归实现类别树示例代码

    在浏览淘宝,京东等各大商场的时候会发现首页一般都是商品分类,并且这个商品分类都是层级关系.下图以天猫商场为例,分为了三层的树状结构!!! 那么这种的类别树是怎么实现的呢?话不多说直接上代码: 1.首先我们新建一张商品类别表并维护所需数据: 2.创建商品类别实体 @Data @EqualsAndHashCode(callSuper = false) @Accessors(chain = true) @ApiModel("商品类别表") public class OrdersCategor

  • java之TreeUtils生成一切对象树形结构案例

    项目中经常会遇到各种需要以树形结构展示的功能,比较常见的,如菜单树,分类树,部门树等等,如果为每种类型都遍历递归生成树形结构返回给前端,显得有些冗余且麻烦,并且其实逻辑都是一致的,只是遍历的对象不同而已,故其实可以通过面向接口思维,来实现这种通用工具类的实现. TreeNode用来表示每个树节点的抽象,即需要生成树的对象需要实现此接口. /** * 树节点父类,所有需要使用{@linkplain TreeUtils}工具类形成树形结构等操作的节点都需要实现该接口 * * @param <T>

  • Java删除二叉搜索树的任意元素的方法详解

    本文实例讲述了Java删除二叉搜索树的任意元素的方法.分享给大家供大家参考,具体如下: 一.删除思路分析 在删除二叉搜索树的任意元素时,会有三种情况: 1.1 删除只有左孩子的节点 节点删除之后,将左孩子所在的二叉树取代其位置:连在原来节点父亲元素右节点的位置,比如在图中需要删除58这个节点. 删除58这个节点后,如下图所示: 1.2 删除只有右孩子的节点: 节点删除之后,将右孩子所在的二叉树取代其位置:连在原来节点的位置,比如在下图中需要删除58这个节点. 删除58这个节点后,如下图所示: 这

  • java栈实现二叉树的非递归遍历的示例代码

    一般来说遍历二叉树用到递归,但是用Stack进行遍历也是一个不错的方法. 二叉树设置 class Node{ public int val; public Node left; public Node right; public Node(int v) { val=v; left=null; right=null; } } public class Main { public static void main(String[] args) { Node head =new Node(0); No

  • Java数据结构之哈夫曼树概述及实现

    一.与哈夫曼树相关的概念 概念 含义 1. 路径 从树中一个结点到另一个结点的分支所构成的路线 2. 路径长度 路径上的分支数目 3. 树的路径长度 长度从根到每个结点的路径长度之和 4. 带权路径长度 结点具有权值, 从该结点到根之间的路径长度乘以结点的权值, 就是该结点的带权路径长度 5. 树的带权路径长度 树中所有叶子结点的带权路径长度之和 二.什么是哈夫曼树 定义: 给定n个权值作为n个叶子结点, 构造出的一棵带权路径长度(WPL)最短的二叉树,叫哈夫曼树(), 也被称为最最优二叉树.

  • Java二叉树的四种遍历(递归和非递归)

    二叉树的遍历可以分为前序.中序.后序.层次遍历. 前中后是指何时访问中间节点,即前序遍历,遍历节点的顺序为:中->左->右: 中序遍历,遍历节点的顺序为:左->中->右: 后序遍历,遍历节点的顺序为:左->右->中. 前序遍历 递归实现 public void preorder_Traversal(TreeNode root) { if(root==null)return; //访问节点的逻辑代码块 System.out.print(root.val+" &q

  • 图文详解JAVA实现哈夫曼树

    前言  我想学过数据结构的小伙伴一定都认识哈夫曼,这位大神发明了大名鼎鼎的"最优二叉树",为了纪念他呢,我们称之为"哈夫曼树".哈夫曼树可以用于哈夫曼编码,编码的话学问可就大了,比如用于压缩,用于密码学等.今天一起来看看哈夫曼树到底是什么东东. 概念 当然,套路之一,首先我们要了解一些基本概念. 1.路径长度:从树中的一个结点到另一个结点之间的分支构成这两个结点的路径,路径上的分支数目称为路径长度. 2.树的路径长度:从树根到每一个结点的路径长度之和,我们所说的完全

  • java二叉树的几种遍历递归与非递归实现代码

    前序(先序)遍历 中序遍历 后续遍历 层序遍历 如图二叉树: 二叉树结点结构 public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x){ val=x; } @Override public String toString(){ return "val: "+val; } } 访问函数 public void visit(TreeNode node){ System.out.print(

  • Java数据结构学习之树

    一.树 1.1 概念 与线性表表示的一一对应的线性关系不同,树表示的是数据元素之间更为复杂的非线性关系. 直观来看,树是以分支关系定义的层次结构. 树在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可以用树的形象来表示. 简单来说,树表示的是1对多的关系. 定义(逻辑结构): 树(Tree)是n( n>=0 )个结点的有限集合,没有结点的树称为空树,在任意一颗非空树中: 有且仅有一个特定的称为根(root)的结点 . 当n>1的时,其余结点可分为 m( m>0 ) 个互不相交的

  • JAVA如何转换树结构数据代码实例

    在实战开发中经常有需要处理树形菜单.树形目录等等等业务需求.而对于这种产品,在设计数据库时也建议使用id<----->parentId的结构来做.但是最终前端显示多用hightChart或者Echart插件来实现.所以在给前端数据时,最好的做法就是把数据库结构话的数据处理成treeJson格式. 第一步:引入fastjson <dependency> <groupId>com.alibaba</groupId> <artifactId>fastj

随机推荐