一、二叉树 说树这种结构之前，我们要先说一下树这种结构存在的意义。在我们的现实场景中，比如图书馆，我们可以根据分类快速找到我们想要找到的书籍。比如我们要找一本叫做《
一、二叉树
说树这种结构之前，我们要先说一下树这种结构存在的意义。在我们的现实场景中，比如图书馆，我们可以根据分类快速找到我们想要找到的书籍。比如我们要找一本叫做《Java编程思想》这本书，我们只需要根据，理工科 ==> 计算机 ==>Java语言分区就可以快速找到我们想要的这本书。这样我们就不需要像数组或者链表这种结构，我们需要遍历一遍才能找到我们想要的东西。再比如，我们所使用的电脑的文件夹目录本身也是一种树的结构。
从上面的描述我们可知，树这种结构具备天然的高效性可以巧妙的避开我们不关心的东西，只需要根据我们的线索快速去定位我们的目标。所以说树代表着一种高效。
在了解二分搜索树之前，我们不得不了解一下二叉树，因为二叉树是实现二分搜索树的基础。就像我们后面会详细讲解和实现AVL（平衡二叉树），红黑树等树结构，你不得不在此之前学习二分搜索树一样，他们都是互为基础的。
1.1 二叉树的定义
二叉树也是一种动态的数据结构。每个节点只有两个叉，也就是两个孩子节点，分别叫做左孩子，右孩子，而没有一个孩子的节点叫做叶子节点。每个节点最多有一个父亲节点，最多有两个孩子节点(也可以没有孩子节点或者只有一个孩子节点)。对于二叉树的定义我们不通过复杂的数学表达式来叙述，而是通过简单的描述，让大家了解一个二叉树长什么样子。
- 1、只有一个根节点。
- 2、每个节点至多有两个孩子节点，分别叫左孩子或者右孩子。(左右孩子节点没有大小之分哦)
- 3、每个子树也都是一个二叉树
满足以上三条定义的就是一个二叉树。如下图所示，就是一颗二叉树
1.2、二叉树的类型
根据二叉树的节点分布大概可以分为以下三种二叉树：完全二叉树，满二叉树，平衡二叉树。对于以下树的描述不使用数学表达式或者专业术语，因为那样很难让人想象到一棵树到底长什么样子。
- 满二叉树：从根节点到每一个叶子节点所经过的节点数都是相同的。
如下图所示就是一颗满二叉树。
- 完全二叉树：除去最后一层叶子节点，就是一颗完全二叉树，并且最后一层的节点只能集中在左侧。
对于上面的性质，我们从另一个角度来说就是将满二叉树的叶子节点从右往左删除若干个后就变成了一棵完全二叉树，也就是说，满二叉树一定是一棵完全二叉树，反之不成立。如下图所示：除了图3都是一棵完全二叉树。
- 平衡二叉树：平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉树，又是一棵二分搜索树，平衡二叉树的任意一个节点的左右两个子树的高度差的绝对值不超过1，即左右两个子树都是一棵平衡二叉树。
二、二分搜索树
特点：
-
动态数据结构。
-
是一颗二叉树。
-
二分搜索树的每个节点的值：
- 每个节点的值都大于其左子树的所有节点的值。
- 每个节点的值都小于其右子树的所有节点的值。
-
每一颗子树也是二分搜索树。
-
存储的元素必须有可比较性，Java中的话就要求二分搜索树保存的数据类型要实现Comparable接口，或者使用额外的比较器实现。
-
一般二分搜索树不包含重复元素，当然也可以定义包含重复元素的二分搜索树。
- 如果想要包含重复元素的话，只需要定义二分搜索树的左节点的值小于等于当前节点的值或右节点的值大于等于当前节点即可。
-
二分搜索树天然的具有递归特性。
三、二分搜索树的实现
3.1、基础结构实现
/** * @Author: huangyibo * @Date: 2022/2/7 23:42 * @Description: 二分搜索树 */ public class BinarySearchTree<E extends Comparable<E>> { //二分搜索树节点类 private class Node<E extends Comparable<E>>{ public E e; public Node<E> left; public Node<E> right; public Node(E e){ this.e = e; this.left = null; this.right = null; } @Override public String toString() { return e.toString(); } } // 根节点 private Node<E> root; // 树容量 private Integer size; public BinarySearchTree(){ root = null; size = 0; } /** * 获取元素个数 * @return */ public int getSize(){ return size; } /** * 返回二分搜索树是否为空 * @return */ public boolean isEmpty(){ return size == 0; } @Override public String toString(){ StringBuilder res = new StringBuilder(); generateBSTString(root, 0, res); return res.toString(); } /** * 生成以node为根节点，深度为depth的描述二叉树的字符串 * @param node * @param depth * @param res */ private void generateBSTString(Node<E> node, int depth, StringBuilder res) { if(node == null){ res.append(generateDepthString(depth) + "null\n"); return; } res.append(generateDepthString(depth) + node.e +"\n"); generateBSTString(node.left, depth + 1, res); generateBSTString(node.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(); } }3.2、添加元素
由于二分搜索树本身的递归特性, 所以可以很方便的使用递归实现向二分搜索树中添加元素, 步骤如下:
-
定义一个公共的add方法, 用于添加元素。
-
定义一个递归的add方法用于实际向二分搜索树中添加元素。
对于这个递归方法，设定的方法语义为，向以node为根节点的树上添加一个元素，并返回插入新节点后的二分搜索树的根节点。
/** * 向二分搜索树添加新的元素 * @param e */ public void add(E e){ //向根节点添加元素e root = add(root, e); } /** * 向以node为根的二分搜索树中插入元素e，递归算法 * @param node * @param e * @return 返回插入新元素的二分搜索树的根 */ private Node<E> add(Node<E> node, E e){ if(node == null){ size ++; return new Node<>(e); } //递归调用，元素添加到node.left if(e.compareTo(node.e) < 0){ node.left = add(node.left, e); }else if(e.compareTo(node.e) > 0){ //递归调用，元素添加到node.right node.right = add(node.right, e); } //返回当前根节点 return node; }3.3、查找元素
由于二分搜索树没有下标，所以针对二分搜索树的查找操作，这里定义一个contains方法，查看二分搜索树是否包含某个元素，返回一个布尔型变量，这个查找的操作一样是一个递归的过程，具体代码实现如下：
/** * 查看二分搜索树是否包含元素 * @param e * @return */ public boolean contains(E e){ return contains(root, e); } /** * 查看以node为根的二分搜索树中是否包含元素e，递归算法 * @param node * @param e * @return */ private boolean contains(Node<E> node, E e){ if(node == null){ return false; } if(e.compareTo(node.e) == 0){ return true; }else if(e.compareTo(node.e) < 0){ return contains(node.left, e); }else{ return contains(node.right, e); } }3.4、遍历操作
-
遍历操作就是把所有的节点都访问一遍
-
访问的原因和业务相关
遍历分类
-
深度优先遍历
-
前序遍历：对当前节点的遍历在对左右孩子节点的遍历之前，遍历顺序：当前节点->左孩子->右孩子
-
中序遍历：对当前节点的遍历在对左右孩子节点的遍历中间，遍历顺序：左孩子->当前节点->右孩子
-
后序遍历：对当前节点的遍历在对左右孩子节点的遍历之后，遍历顺序：左孩子->右孩子->当前节点
-
广度优先遍历
-
层序遍历：按层从左到右进行遍历
3.4.1前序遍历
- 最自然的遍历方式。
- 最常用的遍历方式。
这里一样使用递归来实现遍历，对于一颗二分搜索树进行遍历，如果要使用非递归方式实现的话，可以使用一个栈来赋值进行遍历，代码如下:
/** * 二分搜索树的前序遍历 */ public void preOrder(){ preOrder(root); } /** * 前序遍历以node为根的二分搜索树，递归算法 * @param node */ private void preOrder(Node<E> node){ // 递归终止条件 if(node == null){ return; } // 1. 前序遍历先访问当前节点 System.out.println(node.e); // 2. 前序遍历访问左孩子 preOrder(node.left); // 3. 前序遍历访问右孩子 preOrder(node.right); }非递归写法
/** * 二分搜索树的非递归前序遍历 */ public void preOrderNR(){ Stack<Node<E>> stack = new Stack(); // 首先将根节点压入栈 stack.push(root); while (!stack.isEmpty()){ Node<E> cur = stack.pop(); // 前序遍历当前节点 System.out.println(cur.e); // 由于栈是后入先出, 前序遍历是先左孩子, 再右孩子, 所以这里需要先将右孩子压入栈 if(cur.right != null){ stack.push(cur.right); } if(cur.left != null){ stack.push(cur.left); } } }3.4.2 中序遍历
- 二分搜索树的中序遍历的结果是顺序的。
3.4.3 后序遍历
- 后序遍历的一个应用：为二分搜索树释放内存，Java中其实并不需要手动释放内存。
前、中、后序遍历总结
可以认为在遍历的时候每个节点要访问三次，对当前节点进行遍历操作时一次，访问当前节点左子树时一次，访问当前节点右子树时一次，可以认为前序遍历就是在第一次访问当前节点时进行操作，以方便我们理解遍历结果，下面几张图演示前中后序遍历的访问顺序，蓝色的点表示在这次访问时对当前节点进行遍历操作。
前序遍历示意图
中序遍历示意图
后序遍历示意图
层序遍历
- 按层从左到右进行遍历
- 广度优先遍历
- 针对上面那颗树，遍历结果为 : 28 16 32 13 22 29 42
层序遍历代码实现，使用队列进行辅助实现
/** * 二分搜索树的层序遍历 * 层序遍历, 从左到右一层一层遍历, 借助队列实现 */ public void levelOrder(){ // LinkedList实现了Queue接口 Queue<Node<E>> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()){ Node<E> cur = queue.remove(); System.out.println(cur.e); if(cur.left != null){ queue.add(cur.left); } if(cur.right != null){ queue.add(cur.right); } } }广度优先遍历的意义 :
- 更快找到问题的解
- 常用于算法设计中-最短路径
3.5、删除节点
在删除节点前，先看两种特殊的情况，删除最小节点和删除最大节点。
3.5.1 删除最小值
在删除最小节点之前，先要找到这个最小节点，根据二分搜索树的特性可知，从根节点一直往左找，最后一个没有左子树的节点一定就是整棵树的最小值。
对于删除最小值时，存在两种情况
- 最小值就是一个叶子节点，直接删除该节点即可
- 如果最小值所在的节点还有右子树，则用右子树的根节点替换当前节点即可，如下图所示
3.5.2 删除最大值
最大值的删除和最小值删除原理是一样的，先右找到最后一个没有右子树的节点就是整颗树的最大值，然后进行删除最大值操作：
-
最大值为叶子节点时，直接删除该节点即可
-
最大值所在节点还有左子树时，则使用最大值左子树的根节点替换当前节点即可，如下图所示
3.6 删除任意节点
删除任意节点可以分为以下几种情况：
-
删除叶子节点，直接删除即可
-
删除只有右子树的节点，逻辑同删除最小值，虽然这个节点不一定是最小值，但是删除逻辑是一样的
-
删除只有左子树的节点，逻辑同删除最大值
-
删除同时具有左右子树的节点，这个时候删除节点的步骤稍微复杂一些
- 首先找到要删除的节点
- 然后找到对应节点的前驱或者后继节点，前驱就是指当前节点的左子树中最大的元素节点，后继就是指当前节点右子树中最小的元素节点，下图就是基于后继节点的删除演示
- 使用后继节点替换当前节点，然后再删除要删除的节点
具体代码实现如下 :
/** * 从二分搜索树中删除元素为e的节点 * @param e */ public void remove(E e){ root = remove(root, e); } /** * 删除以node为根的二分搜索树中值为e的节点，递归递归方式 * 返回删除节点后新的二分搜索树的根 * @param node * @param e * @return */ private Node<E> remove(Node<E> node, E e){ //节点为空，直接返回 if(node == null){ return null; } if(e.compareTo(node.e) < 0){ //待删除元素小于当前节点，向左递归寻找 node.left = remove(node.left, e); return node; }else if(e.compareTo(node.e) > 0){ //待删除元素大于当前节点，向右递归寻找 node.right = remove(node.right, e); return node; }else { //待删除节点左子树为空 if(node.left == null){ Node<E> rightNode = node.right; node.right = null; size --; return rightNode; } //待删除节点右子树为空 if(node.right == null){ Node<E> rightNode = node.left; node.left = null; size --; return rightNode; } //待删除节点左、右子树不为空 //找到比待删除节点大的最小节点，即待删除节点右子树最小节点 //用这个节点顶替待删除节点的位置 //找到比待删除节点大的最小节点，即待删除节点右子树最小节点 Node<E> successor = minimum(node.right); //删除比待删除节点大的最小节点，并将返回值给succeer的右孩子 successor.right = removeMin(node.right); //node.left赋值给successor.left successor.left = node.left; //node节点和二分搜索树脱离关系 node.left = node.right = null; return successor; } }至此就完成了整个二分搜索树的全部代码，完整代码如下 :
package com.yibo.datastructure.binarysearchtree; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; /** * @Author: huangyibo * @Date: 2022/2/7 23:42 * @Description: 二分搜索树 */ public class BinarySearchTree<E extends Comparable<E>> { //二分搜索树节点类 private class Node<E extends Comparable<E>>{ public E e; public Node<E> left; public Node<E> right; public Node(E e){ this.e = e; this.left = null; this.right = null; } @Override public String toString() { return e.toString(); } } // 根节点 private Node<E> root; // 树容量 private Integer size; public BinarySearchTree(){ root = null; size = 0; } /** * 获取元素个数 * @return */ public int getSize(){ return size; } /** * 返回二分搜索树是否为空 * @return */ public boolean isEmpty(){ return size == 0; } /** * 向二分搜索树添加新的元素 * @param e */ public void add(E e){ //向根节点添加元素e root = add(root, e); } /** * 向以node为根的二分搜索树中插入元素e，递归算法 * @param node * @param e * @return 返回插入新元素的二分搜索树的根 */ private Node<E> add(Node<E> node, E e){ if(node == null){ size ++; return new Node<>(e); } //递归调用，元素添加到node.left if(e.compareTo(node.e) < 0){ node.left = add(node.left, e); }else if(e.compareTo(node.e) > 0){ //递归调用，元素添加到node.right node.right = add(node.right, e); } //返回当前根节点 return node; } /** * 查看二分搜索树是否包含元素 * @param e * @return */ public boolean contains(E e){ return contains(root, e); } /** * 查看以node为根的二分搜索树中是否包含元素e，递归算法 * @param node * @param e * @return */ private boolean contains(Node<E> node, E e){ if(node == null){ return false; } if(e.compareTo(node.e) == 0){ return true; }else if(e.compareTo(node.e) < 0){ return contains(node.left, e); }else{ return contains(node.right, e); } } /** * 二分搜索树的前序遍历 */ public void preOrder(){ preOrder(root); } /** * 前序遍历以node为根的二分搜索树，递归算法 * @param node */ private void preOrder(Node<E> node){ // 递归终止条件 if(node == null){ return; } // 1. 前序遍历先访问当前节点 System.out.println(node.e); // 2. 前序遍历访问左孩子 preOrder(node.left); // 3. 前序遍历访问右孩子 preOrder(node.right); } /** * 二分搜索树的非递归前序遍历 */ public void preOrderNR(){ Stack<Node<E>> stack = new Stack(); // 首先将根节点压入栈 stack.push(root); while (!stack.isEmpty()){ Node<E> cur = stack.pop(); // 前序遍历当前节点 System.out.println(cur.e); // 由于栈是后入先出, 前序遍历是先左孩子, 再右孩子, 所以这里需要先将右孩子压入栈 if(cur.right != null){ stack.push(cur.right); } if(cur.left != null){ stack.push(cur.left); } } } /** * 二分搜索树的中序遍历 */ public void inOrder(){ inOrder(root); } /** * 中序遍历以node为根的二分搜索树，递归算法 * 中序遍历指的是访问当前元素的顺序放在访问左右子节点之间 * 中序遍历的结果是有序的 * @param node */ private void inOrder(Node<E> node){ // 递归终止条件 if(node == null){ return; } // 1. 中序遍历访问左孩子 inOrder(node.left); // 2. 中序遍历访问当前节点 System.out.println(node.e); // 3. 中序遍历访问右孩子 inOrder(node.right); } /** * 二分搜索树的后序遍历 */ public void postOrder(){ postOrder(root); } /** * 后序遍历以node为根的二分搜索树，递归算法 * 后序遍历指的是访问当前元素的顺序放在访问左右子节点之后 * @param node */ private void postOrder(Node<E> node){ // 递归终止条件 if(node == null){ return; } // 1. 后序遍历访问左孩子 postOrder(node.left); // 2. 后序遍历访问右孩子 postOrder(node.right); // 3. 后序遍历访问当前节点 System.out.println(node.e); } /** * 二分搜索树的层序遍历 * 层序遍历, 从左到右一层一层遍历, 借助队列实现 */ public void levelOrder(){ // LinkedList实现了Queue接口 Queue<Node<E>> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()){ Node<E> cur = queue.remove(); System.out.println(cur.e); if(cur.left != null){ queue.add(cur.left); } if(cur.right != null){ queue.add(cur.right); } } } /** * 寻找二分搜索树中的最小元素, 递归方式 * @return */ public E minimum(){ if(size == 0){ throw new IllegalArgumentException("BST is empty."); } return minimum(root).e; } /** * 返回以node为根的二分搜索树的最小值所在的节点 * @param node * @return */ private Node<E> minimum(Node<E> node){ if(node.left == null){ return node; } return minimum(node.left); } /** * 寻找二分搜索树中的最小元素, 非递归方式 * @return */ public E minimumNR(){ if(size == 0){ throw new IllegalArgumentException("BST is empty."); } Node<E> cur = root; while (cur.left != null){ cur = cur.left; } return cur.e; } /** * 寻找二分搜索树中的最小元素, 递归方式 * @return */ public E maximum(){ if(size == 0){ throw new IllegalArgumentException("BST is empty."); } return maximum(root).e; } /** * 返回以node为根的二分搜索树的最小值所在的节点 * @param node * @return */ private Node<E> maximum(Node<E> node){ if(node.right == null){ return node; } return maximum(node.right); } /** * 寻找二分搜索树中的最小元素, 非递归方式 * @return */ public E maximumNR(){ if(size == 0){ throw new IllegalArgumentException("BST is empty."); } Node<E> cur = root; while (cur.right != null){ cur = cur.right; } return cur.e; } /** * 从二分搜索树中删除最小值所在节点，并返回最小值 * @return */ public E removeMin(){ E ret = minimum(); root = removeMin(root); return ret; } /** * 删除以node为根的二分搜索树中的最小节点， * 返回删除节点后新的二分搜索树的根 * @param node * @return */ private Node<E> removeMin(Node<E> node){ if(node.left == null){ Node<E> rightNode = node.right; node.right = null; size --; return rightNode; } //递归调用node.left node.left = removeMin(node.left); return node; } /** * 从二分搜索树中删除最大值所在节点，并返回最大值 * @return */ public E removeMax(){ E ret = maximum(); root = removeMax(root); return ret; } /** * 删除以node为根的二分搜索树中的最大节点， * 返回删除节点后新的二分搜索树的根 * @param node * @return */ private Node<E> removeMax(Node<E> node){ if(node.right == null){ Node<E> rightNode = node.left; node.left = null; size --; return rightNode; } //递归调用node.right node.right = removeMax(node.right); return node; } /** * 从二分搜索树中删除元素为e的节点 * @param e */ public void remove(E e){ root = remove(root, e); } /** * 删除以node为根的二分搜索树中值为e的节点，递归递归方式 * 返回删除节点后新的二分搜索树的根 * @param node * @param e * @return */ private Node<E> remove(Node<E> node, E e){ //节点为空，直接返回 if(node == null){ return null; } if(e.compareTo(node.e) < 0){ //待删除元素小于当前节点，向左递归寻找 node.left = remove(node.left, e); return node; }else if(e.compareTo(node.e) > 0){ //待删除元素大于当前节点，向右递归寻找 node.right = remove(node.right, e); return node; }else { //待删除节点左子树为空 if(node.left == null){ Node<E> rightNode = node.right; node.right = null; size --; return rightNode; } //待删除节点右子树为空 if(node.right == null){ Node<E> rightNode = node.left; node.left = null; size --; return rightNode; } //待删除节点左、右子树不为空 //找到比待删除节点大的最小节点，即待删除节点右子树最小节点 //用这个节点顶替待删除节点的位置 //找到比待删除节点大的最小节点，即待删除节点右子树最小节点 Node<E> successor = minimum(node.right); //删除比待删除节点大的最小节点，并将返回值给succeer的右孩子 successor.right = removeMin(node.right); //node.left赋值给successor.left successor.left = node.left; //node节点和二分搜索树脱离关系 node.left = node.right = null; return successor; } } @Override public String toString(){ StringBuilder res = new StringBuilder(); generateBSTString(root, 0, res); return res.toString(); } /** * 生成以node为根节点，深度为depth的描述二叉树的字符串 * @param node * @param depth * @param res */ private void generateBSTString(Node<E> node, int depth, StringBuilder res) { if(node == null){ res.append(generateDepthString(depth) + "null\n"); return; } res.append(generateDepthString(depth) + node.e +"\n"); generateBSTString(node.left, depth + 1, res); generateBSTString(node.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(); } }测试代码
public class Test { public static void main(String[] args) { test1(); BinarySearchTree<Integer> bst = new BinarySearchTree<>(); Random random = new Random(); for (int i = 0; i < 1000; i++) { bst.add(random.nextInt(10000)); } ArrayList<Integer> arrayList = new ArrayList<>(); while (!bst.isEmpty()){ arrayList.add(bst.removeMin()); } for (int i = 1; i < arrayList.size(); i++) { if(arrayList.get(i - 1) > arrayList.get(i)){ throw new RuntimeException("Error"); } } System.out.println("removeMin test completed."); } private static void test1() { BinarySearchTree<Integer> bst = new BinarySearchTree<>(); int[] nums = {5, 3, 6, 8 ,4 ,2}; for (int num : nums) { bst.add(num); } bst.preOrder(); System.out.println("=================="); bst.preOrderNR(); System.out.println("=================="); bst.inOrder(); System.out.println("=================="); bst.postOrder(); System.out.println("=================="); bst.levelOrder(); System.out.println("=================="); bst.inOrder(); System.out.println("=================="); bst.remove(5); bst.inOrder(); System.out.println("=================="); System.out.println(bst); } }参考： https://www.cnblogs.com/hello-shf/p/11342907.html
https://blog.csdn.net/love905661433/article/details/82981527