数据结构基础：Java版手撕BST二叉搜索树（含前序、中序、后序、层序遍历，树的高度计算）

2023-10-25 21:32
文章标签 java 基础 中序 遍历 计算 数据结构 搜索 层序 二叉 高度 后序 前序 bst 版手

本文主要是介绍数据结构基础：Java版手撕BST二叉搜索树（含前序、中序、后序、层序遍历，树的高度计算），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前传

文章中的图形化演示请在下述网址模拟：
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

一、BST概述

和链表一样，二叉搜索树也是一种动态数据结构。但其查询效率更高，查询的均摊时间复杂度为O(logn)。
在这里插入图片描述

二叉搜索树的特点：

  1. 只有一个根节点，每个节点最多有两个孩子节点，每个节点最多只有一个父节点。
  2. 二叉搜索树具有天然递归结构。每个节点的左/右子树也是二叉搜索树。
  3. 二叉搜索树的每个节点的值大于左子树所有节点的值，小于右子树所有节点的值。
  4. 存储的元素必须具有可比性，即实现Comparable接口。
  5. 在极端情况BST会变成链表结构。
  6. 二分搜索树可以支持重复元素。

在这里插入图片描述

二叉搜索树的遍历：

  • 前序遍历：跟节点 – 左子节点 – 右子节点
  • 中序遍历：左子节点 – 根节点 – 右子节点
    二分搜索树排序过后的结果。
  • 后序遍历：左子节点 – 右子节点 --跟节点

我们代码的版本是不允许插入重复元素的。像下图所示，其支持重复插入数据的版本也只是简单的在已存在节点的右子树上创建一个新节点。
在这里插入图片描述
删除重复节点是将第一个找到的节点删除。
在这里插入图片描述

二、代码实现

1、树通用接口

package com.saint.base.datastructure.tree;/*** 树接口** @author Saint* @version 1.0* @createTime 2021-09-09 8:43*/
public interface Tree<E> {/*** 元素个数** @return int*/int size();/*** 添加元素** @param e*/void add(E e);/*** 删除元素** @param e*/void remove(E e);/*** 树中是否包含元素e** @param e* @return boolean*/boolean contains(E e);}

2、树节点

package com.saint.base.datastructure.tree;/*** 树节点** @author Saint* @version 1.0* @createTime 2021-09-09 8:43*/
public class TreeNode<E> {/*** 用于存放数据*/public E e;/*** 左子节点*/public TreeNode left;/*** 右子节点*/public TreeNode right;public TreeNode(E e) {this.e = e;this.left = null;this.right = null;}
}

3、BST实现

package com.saint.base.datastructure.tree;import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;/*** 二分搜索树** @author Saint*/
public class BSTree<E extends Comparable<E>> implements Tree<E> {/*** 树容器*/TreeNode<E> root;/*** 树节点个数*/int size;public BSTree() {root = null;size = 0;}@Overridepublic void add(E e) {root = add(root, e);}/*** 往指定树中添加节点** @param node* @param e* @return*/private TreeNode<E> add(TreeNode<E> node, E e) {// 如果树节点为null,新建节点if (null == node) {size++;return new TreeNode<>(e);}// 要添加的数据小于根节点，则插入到node的左子树if (e.compareTo(node.e) < 0) {node.left = add(node.left, e);} else if (e.compareTo(node.e) > 0) {node.right = add(node.right, e);} else {// do nothing, e的值和node.e相等时不做任何操作，这里大家可以自定义操作}// 递归返回当前跟节点return node;}@Overridepublic void remove(E e) {root = remove(root, e);}private TreeNode<E> remove(TreeNode<E> node, E e) {if (null == node) {throw new RuntimeException("BST is empty!");}// 如果要删除的节点值比node节点值小if (e.compareTo(node.e) < 0) {node.left = remove(node.left, e);return node;} else if (e.compareTo(node.e) > 0) {// 如果要删除的节点值比node节点值大node.right = remove(node.right, e);return node;} else {// 要删除的节点就是当前节点// 下面要分三种情况进行考虑：node的左子树为null，node的右子树为null，node的左右子树都不为null。// 1）node的左子树为nullif (node.left == null) {TreeNode<E> rightNode = node.right;node.right = null;size--;return rightNode;}// 2）node的右子树为nullif (node.right == null) {TreeNode<E> leftNode = node.left;node.left = null;size--;return leftNode;}// 3）node的左右子树都不为null// 我们的思路是：1.获取node右子树的最小值做为新树的根节点newNode// 2.然后将node右子树中的最小值从右子树中删除。// 3.然后将node.left 和 node.right(移除最小值之后)的树结构分别挂在newNode的左右子树上。TreeNode<E> newNode = minimum(node.right);// removeMin()方法里进行了size --TreeNode<E> rightNode = removeMin(node.right);newNode.left = node.left;node.left = null;node.right = null;newNode.right = rightNode;return newNode;}}/*** 移除node树中的最小值** @param node* @return*/public TreeNode<E> removeMin(TreeNode<E> node) {if (node.left == null) {TreeNode<E> rightNode = node.right;node.right = null;size--;return rightNode;}return removeMin(node.left);}/*** 移除node树的最大值** @param node* @return*/public TreeNode<E> removeMax(TreeNode<E> node) {if (null == node.right) {TreeNode<E> leftNode = node.left;node.left = null;size--;return leftNode;}return removeMax(node.right);}@Overridepublic boolean contains(E e) {return contains(root, e);}private boolean contains(TreeNode<E> node, E e) {if (null == node) {return false;}if (e.compareTo(node.e) < 0) {return contains(node.left, e);} else if (e.compareTo(node.e) > 0) {return contains(node.right, e);}return true;}/*** 获取BST树的最大值** @return*/public E maximum() {if (size == 0) {throw new RuntimeException("BST is empty!");}return maximum(root).e;}private TreeNode<E> maximum(TreeNode<E> node) {if (node.right == null) {return node;}return maximum(node.right);}/*** 获取树的最小值** @return*/public E minimum() {if (size == 0) {throw new RuntimeException("BST is empty!");}return minimum(root).e;}private TreeNode<E> minimum(TreeNode<E> node) {if (node.left == null) {return node;}return minimum(node.left);}@Overridepublic int size() {return size;}/*** 树的高度** @return*/public void height() {System.out.println("----树的高度----");System.out.println("DFS方式：" + getHeightDFS(root));System.out.println("BFS方式：" + getHeightBFS(root));}@Overridepublic String toString() {StringBuilder res = new StringBuilder();generateBSTString(root, 0, res);return res.toString();}private void generateBSTString(TreeNode<E> root, int depth, StringBuilder res) {if (root == null) {return;}res.append(generateDepthString(depth) + root.e + "\n");generateBSTString(root.left, depth + 1, res);generateBSTString(root.right, depth + 1, res);}private String generateDepthString(int depth) {StringBuilder res = new StringBuilder();for (int i = 0; i < depth; i++) {res.append("--");}return res.toString();}}

4、树的遍历–DFS

树的很多操作都是基于树的遍历。由于树的前序遍历规则是跟左右，所以针对前序遍历我们有两种方式：递归和非递归。而中序遍历、后续遍历则只能递归。

/*** BST的前序遍历 -- 跟左右*/
public void preOrder() {System.out.println("递归方式的前序遍历");preOrder(root);System.out.println();System.out.println("非递归方式的前序遍历：");preOrderNR(root);System.out.println();}/*** 递归方式的前序遍历** @param node*/
private void preOrder(TreeNode<E> node) {if (null == node) {return;}// 此处的输出可以使用业务逻辑替代。System.out.print(node.e + " ");preOrder(node.left);preOrder(node.right);
}/*** 非递归方式的前序遍历** @param root*/
private void preOrderNR(TreeNode<E> root) {Stack<TreeNode<E>> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode<E> popNode = stack.pop();// 此处的输出可以使用业务逻辑替代。System.out.print(popNode.e + " ");// 因为栈是先进后出的，而前序遍历是跟左右，所以我们先将当前节点的右子树放进栈。if (popNode.right != null) {stack.push(popNode.right);}if (popNode.left != null) {stack.push(popNode.left);}}
}/*** BST的中序遍历 -- 左跟右*/
public void inOrder() {System.out.println("递归方式的中序遍历:");inOrder(root);System.out.println();}/*** 递归方式的中序遍历** @param node*/
private void inOrder(TreeNode<E> node) {if (null == node) {return;}inOrder(node.left);// 此处的输出可以使用业务逻辑替代。System.out.print(node.e + " ");inOrder(node.right);
}/*** BST的后序遍历 -- 左右根*/
public void postOrder() {System.out.println("递归方式的后序遍历:");postOrder(root);System.out.println();}/*** 递归方式的后序遍历** @param node*/
private void postOrder(TreeNode<E> node) {if (null == node) {return;}postOrder(node.left);postOrder(node.right);// 此处的输出可以使用业务逻辑替代。System.out.print(node.e + " ");
}

5、树的遍历–BFS

树的前序遍历递归方式实际也可以看做是一种特殊的BFS，
BFS的要旨是一层一层遍历树。

/*** 广度遍历*/
public void levelOrder() {System.out.println("广度遍历:");Queue<TreeNode<E>> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {TreeNode<E> cur = queue.remove();System.out.print(cur.e + " ");if (cur.left != null) {queue.add(cur.left);}if (cur.right != null) {queue.add(cur.right);}}
}

6、树的高度

同样的获取树的高度我们可以采用DFS或BFS。DFS只需找到路径最深的一纵节点（从上到下）；BFS是在逐层遍历时，记录下一共有多少层。

DFS：

/*** DFS -- 获取树的高度** @param node* @return*/
public int getHeightDFS(TreeNode<E> node) {if (null == node) {return 0;}return Math.max(getHeightDFS(node.left), getHeightDFS(node.right)) + 1;
}

BFS:

/*** BFS -- 获取树的高度** @param node* @return*/
public int getHeightBFS(TreeNode<E> node) {Queue<TreeNode<E>> queue = new LinkedList<>();queue.add(node);// 树的高度int height = 0;// 用于遍历每一层数据的队列Queue<TreeNode<E>> temp;while (!queue.isEmpty()) {temp = new LinkedList<>();for (TreeNode<E> cur : queue) {if (cur.left != null) {temp.add(cur.left);}if (cur.right != null) {temp.add(cur.right);}}height++;queue = temp;}return height;
}

7、测试

package com.saint.base.datastructure.tree;/*** @author Saint*/
public class BSTreeTest {public static void main(String[] args) {BSTree<Integer> bsTree = new BSTree<>();bsTree.add(4);System.out.println("after add, root is : \n" + bsTree.toString());System.out.println();bsTree.add(2);System.out.println("after add, root is : \n" + bsTree.toString());System.out.println();bsTree.add(6);System.out.println("after add, root is : \n" + bsTree.toString());System.out.println();bsTree.add(1);System.out.println("after add, root is : \n" + bsTree.toString());System.out.println();bsTree.add(3);System.out.println("after add, root is : \n" + bsTree.toString());System.out.println();bsTree.add(5);System.out.println("after add, root is : \n" + bsTree.toString());System.out.println();bsTree.add(7);System.out.println("after add, root is : \n" + bsTree.toString());System.out.println();bsTree.add(8);System.out.println("after add, root is : \n" + bsTree.toString());// 前序遍历bsTree.preOrder();// 中序遍历bsTree.inOrder();// 后序遍历bsTree.postOrder();// 广度遍历bsTree.levelOrder();// 树的高度bsTree.height();// 删除一个既有左子树又有右子树的节点bsTree.remove(6);System.out.println("after remove, root is : \n" + bsTree.toString());}
}

此时的树结构为：
在这里插入图片描述
1）当我们删除节点006时：
我们的删除节点版本和网站的删除也是不一样的，它是直接把左子树的最大值当做根节点的，而我们是把右子树中的最小值当做根节点。有兴趣的老哥们可以自己实现一把，基础方法我们都已经有了。
在这里插入图片描述
在这里插入图片描述
另外集中删除方式就咕咕咕了
在这里插入图片描述
还是简单说一下吧：

bsTree.remove(1);
// 删除右子树不为null的节点
bsTree.remove(3);

bsTree.remove(1);
// 删除左子树不为null的节点
bsTree.remove(2);

控制台输出：

after add, root is : 
4after add, root is : 
4
--2after add, root is : 
4
--2
--6after add, root is : 
4
--2
----1
--6after add, root is : 
4
--2
----1
----3
--6after add, root is : 
4
--2
----1
----3
--6
----5after add, root is : 
4
--2
----1
----3
--6
----5
----7after add, root is : 
4
--2
----1
----3
--6
----5
----7
------8递归方式的前序遍历
4 2 1 3 6 5 7 8 
非递归方式的前序遍历：
4 2 1 3 6 5 7 8 
递归方式的中序遍历:
1 2 3 4 5 6 7 8 
递归方式的后序遍历:
1 3 2 5 8 7 6 4 
广度遍历:
4 2 6 1 3 5 7 8 ----树的高度----
DFS方式：4
BFS方式：4
after remove, root is : 
4
--2
----1
----3
--7
----5
----8

LeetCode中体现

像计算树的高度；数据的DFS、BFS遍历；树的前中后序遍历在leetcode中都有体现：
二叉树的深度
二叉树的中序遍历
二叉树的后序遍历
二叉树的层序遍历

进阶版的大家可以先尝试自己做一下下面三道题：
在这里插入图片描述

这篇关于数据结构基础：Java版手撕BST二叉搜索树（含前序、中序、后序、层序遍历，树的高度计算）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/285276。

相关文章

Spring MVC如何设置响应

Spring MVC如何设置响应

《SpringMVC如何设置响应》本文介绍了如何在Spring框架中设置响应,并通过不同的注解返回静态页面、HTML片段和JSON数据,此外,还讲解了如何设置响应的状态码和Header... 目录1. 返回静态页面1.1 Spring 默认扫描路径1.2 @RestController2. 返回 html2
阅读更多...
Spring常见错误之Web嵌套对象校验失效解决办法

Spring常见错误之Web嵌套对象校验失效解决办法

《Spring常见错误之Web嵌套对象校验失效解决办法》：本文主要介绍Spring常见错误之Web嵌套对象校验失效解决的相关资料,通过在Phone对象上添加@Valid注解,问题得以解决,需要的朋... 目录问题复现案例解析问题修正总结  问题复现当开发一个学籍管理系统时，我们会提供了一个 API 接口去
阅读更多...
Java操作ElasticSearch的实例详解

Java操作ElasticSearch的实例详解

《Java操作ElasticSearch的实例详解》Elasticsearch是一个分布式的搜索和分析引擎,广泛用于全文搜索、日志分析等场景,本文将介绍如何在Java应用中使用Elastics... 目录简介环境准备1. 安装 Elasticsearch2. 添加依赖连接 Elasticsearch1. 创
阅读更多...
Spring核心思想之浅谈IoC容器与依赖倒置(DI)

Spring核心思想之浅谈IoC容器与依赖倒置(DI)

《Spring核心思想之浅谈IoC容器与依赖倒置(DI)》文章介绍了Spring的IoC和DI机制,以及MyBatis的动态代理,通过注解和反射,Spring能够自动管理对象的创建和依赖注入,而MyB... 目录一、控制反转 IoC二、依赖倒置 DI1. 详细概念2. Spring 中 DI 的实现原理三、
阅读更多...
SpringBoot 整合 Grizzly的过程

SpringBoot 整合 Grizzly的过程

《SpringBoot整合Grizzly的过程》Grizzly是一个高性能的、异步的、非阻塞的HTTP服务器框架,它可以与SpringBoot一起提供比传统的Tomcat或Jet... 目录为什么选择 Grizzly？Spring Boot + Grizzly 整合的优势添加依赖自定义 Grizzly 作为
阅读更多...
使用C#代码计算数学表达式实例

使用C#代码计算数学表达式实例

《使用C#代码计算数学表达式实例》这段文字主要讲述了如何使用C#语言来计算数学表达式,该程序通过使用Dictionary保存变量,定义了运算符优先级,并实现了EvaluateExpression方法来... 目录C#代码计算数学表达式该方法很长，因此我将分段描述下面的代码片段显示了下一步以下代码显示该方法如
阅读更多...
Java后端接口中提取请求头中的Cookie和Token的方法

Java后端接口中提取请求头中的Cookie和Token的方法

《Java后端接口中提取请求头中的Cookie和Token的方法》在现代Web开发中,HTTP请求头（Header）是客户端与服务器之间传递信息的重要方式之一,本文将详细介绍如何在Java后端（以Sp... 目录引言1. 背景1.1 什么是 HTTP 请求头？1.2 为什么需要提取请求头？2. 使用 Spr
阅读更多...
Java如何通过反射机制获取数据类对象的属性及方法

Java如何通过反射机制获取数据类对象的属性及方法

《Java如何通过反射机制获取数据类对象的属性及方法》文章介绍了如何使用Java反射机制获取类对象的所有属性及其对应的get、set方法,以及如何通过反射机制实现类对象的实例化,感兴趣的朋友跟随小编一... 目录一、通过反射机制获取类对象的所有属性以及相应的get、set方法1.遍历类对象的所有属性2.获取
阅读更多...
Java中的Opencv简介与开发环境部署方法

Java中的Opencv简介与开发环境部署方法

《Java中的Opencv简介与开发环境部署方法》OpenCV是一个开源的计算机视觉和图像处理库,提供了丰富的图像处理算法和工具,它支持多种图像处理和计算机视觉算法,可以用于物体识别与跟踪、图像分割与... 目录1.Opencv简介Opencv的应用2.Java使用OpenCV进行图像操作opencv安装j
阅读更多...
java Stream操作转换方法

java Stream操作转换方法

《javaStream操作转换方法》文章总结了Java8中流(Stream)API的多种常用方法,包括创建流、过滤、遍历、分组、排序、去重、查找、匹配、转换、归约、打印日志、最大最小值、统计、连接、... 目录流创建1、list 转 map2、filter（）过滤3、foreach遍历4、groupingB
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2