什么是二叉查找树？看完这篇就懂了
本摘要总结了二叉查找树的相关知识：
定义：
二叉查找树（Binary Search Tree, BST）是一种特殊的二叉树，其左子树的所有节点值均小于根节点的值，右子树的所有节点值均大于根节点的值。这种特性使得BST在查找操作中具有高效性。
性质：
- 若它的左子树不空，则左子树上所有节点的值均小于它根节点的值。
- 若它的右子树不空，则右子树上所有节点的值均大于它根节点的值。
- 它的中序遍历是一个递增序列。
查找：
查找操作基于递归或迭代方法进行：- 递归实现：通过比较目标值与当前节点的关系，向左或向右子树继续搜索。
- 迭代实现：使用循环结构逐步调整指针找到目标节点。
插入：
插入操作根据目标位置的不同分为以下几种情况：- 插入叶子结点。
- 插入仅有一个子树的情况。
- 插入具有两个子树的情况，并通过找到右子树中的最小节点进行替换。
删除：
删除操作较为复杂：- 当被删除结点为叶子结点时直接删除。
- 当被删除结点仅有一个子树时直接替换。
- 当被删除结点有两个子树时需找到后继者进行替换，并调整指针关系。
最小/最大节点：
查找最小或最大节点的方法是不断往左或往右移动直到叶子结点为止。
完整代码：
包括构建BST、查找、插入、删除等方法的具体实现。
目录
-
-
- 1、什么是二叉查找树？
-
- （1）简介
-
（2）性质
- 2、二叉查找树的查找
-
- （1）递归实现
-
（2）迭代实现
- 3、二叉查找树的插入
-
- （1）二叉树的构建
-
（2）二叉树插入操作
-
-
4、二叉查找树的删除操作通常遵循以下步骤：
-
（1）待删节点处于叶子位置
-
（2）待删节点A仅具有单一子节点
-
（3）待删节点A同时拥有左子树和右子树
-
（4）代码实现的具体细节见附录
- 5、二叉查找树的查找最小节点
- 6、二叉查找树的查找最大节点
- 7、完整代码
-
1、什么是二叉查找树？
（1）简介
该算法基于BST（二叉搜索树）模型构建数据结构，并采用分治策略实现高效的插入、删除和查找操作。
（2）性质
当该节点具有非空左子_(时(在其((((((
左(__(_ subtree上的每一个数据字段必定小于该节点的数据字段。
)
类似地，
当该节点拥有非空_right_subtree时，
其中在_right_subtree中的每一个数据字段必定大于该节点的数据字段。
)
而这两部分分别作为左右_subtree则各自构成完整的二叉排序结构。
其基本特征是所有左子节点值小于根节点值而所有右子节点值大于根节点值，并且其核心属性是其中序遍历结果呈现严格递增趋势。
2、二叉查找树的查找
它此类数据结构因其别名而闻名，在实际应用中无疑将为我们带来极大的便利！其基本特性已经被详细阐述因而执行查找操作相对来说较为便捷：当我们访问某个节点时若当前节点的值与目标值相等则立即返回；若当前节点的值小于目标值则转向其右子树继续搜索；反之亦然可采用递归或迭代的方式实现这一过程让我们尝试在该二叉搜索树中寻找数值7
第一步, 查看根节点8的位置。
依据规则, 数值1小于当前节点值2, 因此若想找到数值1的存在位置, 应该位于当前节点的左侧子树中。
进入3后发现数值1大于当前值2, 接着查看2的右子树。
进入6后发现数值1大于当前值2, 继续查看6的右子树。
进入节点5时发现数值等于目标值。
因此算法停止并返回成功。
首先定义二叉树的节点
/** * 二叉树的基本操作
*/
class TreeNode1 {
//节点值
int data;
//左子树的根
TreeNode1 left;
//右子树的根
TreeNode1 right;
public TreeNode1(){}
public TreeNode1(int data) {
this.data = data;
}
@Override
public String toString() {
return "TreeNode1{" +
"data=" + data +
'}';
}
}
AI助手（1）递归实现
- 实现逻辑如下：
1、实现一个递归函数
//参数说明：value表示待查找的目标值；node表示以node节点为首的树结构
//返回值：成功查找到则返回对应节点；若未找到则返回null
public TreeNode findInternal(int value,TreeNode node);2、确定递归终止条件
（1）输入参数中的node指针为空
（2）输入参数中的node指针所指节点的值与目标值一致
- 代码实现
public TreeNode find1(int value) {
return findInternal(value, root);
}
private TreeNode findInternal(int value, TreeNode node) {
//递归终止条件
if (node == null) return null;
if (node.data == value) return node;
if (node.data > value) {
return findInternal(value, node.left);
} else {
return findInternal(value, node.right);
}
}
AI助手（2）迭代实现
- 实现逻辑如下：
1、实现迭代查找算法
//参数说明：value表示目标值
public List< TreeNode1 > find(int value)
2、在处理可能出现多个相同结果的情况下（即重复元素查找），若找到与目标值相等的节点，则将其加入结果列表，并继续探索右子树以寻找可能存在的其他匹配项
- 代码实现
/** * 二叉树查找---迭代实现
*/
public List<TreeNode1> find(int value) {
List<TreeNode1> listTreeNode1 = new ArrayList<>();
TreeNode1 p = root;
while (p != null) {
//如果找到相等的，则加入到返回结果，同时继续去右子树查找
if (p.data == value) {
listTreeNode1.add(p);
p = p.right;
} else if (p.data < value) {
p = p.right;
} else {
p = p.left;
}
}
return listTreeNode1;
}
AI助手3、二叉查找树的插入
（1）二叉树的构建
假设我们有以下数据，我们按从左到右的顺序来构建二叉排序树：
通过二叉树性质的逻辑，这颗二叉树的构建可以通过下图实现
（2）二叉树插入操作
在二叉查找树中，新插入的数据主要集中在叶子节点的位置上。因此，在进行新数据的插入操作时，只需从根节点出发，并根据目标数据与各节点值的高低顺序依次进行判断。
（1）在遍历该二叉搜索树时发现某个节点与其键值相匹配待插入的关键字则操作终止
（2）若新关键字大于当前节点的关键字：
- 若右子树为空则将新节点设为当前节点之右孩子
- 若右子树非空则继续按相同逻辑递归地进行比较最终定位到合适位置例如下图所示当需要插入元素15时按照上述规则可确定其应放置于根节点右侧
（3）如果插入的值比节点的值小：
- 如果左子树为空，则直接设置为左子树
- 如果左子树不为空，则继续查找，直到找到合适的插入位置，比如下图的树，当要插入元素9
- 代码实现
/** * 二叉树插入
*/
public void insert(int value) {
//树没有初始化
if (root == null) {
root = new TreeNode1(value);
return;
}
TreeNode1 p = root;
while (p != null) {
if (p.data <= value) {
if (p.right == null) {
TreeNode1 newNode = new TreeNode1(value);
p.right = newNode;
return;
}
p = p.right;
} else {
if (p.left == null) {
TreeNode1 newNode = new TreeNode1(value);
p.left = newNode;
return;
}
p = p.left;
}
}
}
AI助手4、二叉查找树的删除
相比插入和查找操作而言，二叉查找树的删除操作在算法实现上稍有复杂性。具体问题在于，在删除某个节点后，需要从剩余的节点中选择一个合适的节点来进行代入。这通常需要根据具体的情况进行分类讨论。
（1）被删除结点为叶子结点
举个例子来说吧，在第7位元素的位置上。这种情形下删掉也比较简单。无需过多考虑，在二叉排序树中进行操作。
（2）被删除结点A仅有一个节点
分为两种情况：
-
若仅有左子节点，则需使该节点与其父节点建立关联，并随后移除A结点；
-
若无右子节点，则需使该节点与其父节点建立关联，并随后移除A结点。
- 例如删除元素 14：先把10指向14的右指针移动，去指向13，然后再删除14
- 例如删除元素 10：先把8指向10的右指针移动，去指向14，然后再删除10
（3）被删除结点左右孩子都在
- 第一种情况：删除根节点
例如我删除根节点 8，那么我们只有用 7 或者 10 来替换 8 原来的位置。
（1）我们先看7来顶替位置
（2）我们再看10来顶替位置
是否有疑问？为什么选择使用7或10来替代8？
- 第二种情况：不是根节点
处理方法和第一种情况一样
（4）代码实现
/** * 二叉树删除
*/
public void delete(int value) {
//p 表示指向要删除的节点，初始化指向跟结点
TreeNode1 p = root;
//pp 表示指向p的父节点
TreeNode1 pp = null;
while (p != null && p.data != value) {
pp = p;
if (value > p.data) p = p.right;
else p = p.left;
}
//没有找到节点p
if (p == null) {
return;
}
//要删除的节点有两个子节点
if (p.left != null && p.right != null) {
TreeNode1 minP = p.right;
TreeNode1 minPP = p;
while (minP.left != null) {
minPP = minP;
minP = minP.left;
}
//值替换
p.data = minP.data;
//下面变为删除minP了
p = minP;
pp = minPP;
}
//删除结点是叶子节点或者仅有一个子节点
TreeNode1 child;
if (p.left != null) {
child = p.left;
} else if (p.right != null) {
child = p.right;
} else child = null;
//删除根结点
if (pp == null) root = child;
else if (pp.left == p) pp.left = child;
else pp.right = child;
}
AI助手5、二叉查找树的查找最小节点
基于二叉查找树的特点，在每个节点中都具有明确的位置关系：每个父节点的所有左子树上的节点值均小于该父节点对应的值；反之，在右子树上的所有节点值均大于该父节点对应的值。因此，在寻找最小值的过程中，则需要持续向左移动至某一个特定情况：要么遇到一个无左孩子的中间结点；要么继续深入到叶子结点位置。
- 代码实现
/** * 查找二叉树---最小节点
*/
public TreeNode1 findMin() {
if (root == null) {
return null;
}
//一直往左找左节点
TreeNode1 node = root;
while (node.left != null) {
node = node.left;
}
return node;
}
AI助手6、二叉查找树的查找最大节点
确定当前最大的节点与最小的值具有相似的过程。确定当前最大的节点的过程通常通过沿着右指针不断深入来实现，直到左指针为空或遍历至叶子节点为止。
- 代码实现
/** * 查找二叉树---最大节点
*/
public TreeNode1 findMax() {
if (root == null) {
return null;
}
//一直往右找左节点
TreeNode1 node = root;
while (node.right != null) {
node = node.right;
}
return node;
}
AI助手7、完整代码
package Algorithm.tree;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/** * 二叉树的基本操作
*/
class TreeNode1 {
//节点值
int data;
//左子树的根
TreeNode1 left;
//右子树的根
TreeNode1 right;
public TreeNode1(){}
public TreeNode1(int data) {
this.data = data;
}
@Override
public String toString() {
return "TreeNode1{" +
"data=" + data +
'}';
}
}
public class BinarySearchTree {
private TreeNode1 root;
//建立一个简单的二叉树
public void buildTree(){
TreeNode1 node=new TreeNode1(8);
TreeNode1 node1=new TreeNode1(3);
TreeNode1 node2=new TreeNode1(10);
TreeNode1 node3=new TreeNode1(1);
TreeNode1 node4=new TreeNode1(6);
TreeNode1 node6=new TreeNode1(14);
TreeNode1 node9=new TreeNode1(4);
TreeNode1 node10=new TreeNode1(7);
TreeNode1 node11=new TreeNode1(13);
//连接二叉树
node.left=node1;
node.right=node2;
node1.left=node3;
node1.right=node4;
node2.right=node6;
node4.left=node9;
node4.right=node10;
node6.left=node11;
root=node;
}
/** * 二叉树查找---迭代实现
*/
public List<TreeNode1> find(int value) {
List<TreeNode1> listTreeNode1 = new ArrayList<>();
TreeNode1 p = root;
while (p != null) {
//如果找到相等的，则加入到返回结果，同时继续去右子树查找
if (p.data == value) {
listTreeNode1.add(p);
p = p.right;
} else if (p.data < value) {
p = p.right;
} else {
p = p.left;
}
}
return listTreeNode1;
}
public TreeNode1 find1(int value) {
return findInternal(value, root);
}
private TreeNode1 findInternal(int value, TreeNode1 node) {
//递归终止条件
if (node == null) return null;
if (node.data == value) return node;
if (node.data > value) {
return findInternal(value, node.left);
} else {
return findInternal(value, node.right);
}
}
/** * 二叉树插入
*/
public void insert(int value) {
//树没有初始化
if (root == null) {
root = new TreeNode1(value);
return;
}
TreeNode1 p = root;
while (p != null) {
if (p.data <= value) {
if (p.right == null) {
TreeNode1 newNode = new TreeNode1(value);
p.right = newNode;
return;
}
p = p.right;
} else {
if (p.left == null) {
TreeNode1 newNode = new TreeNode1(value);
p.left = newNode;
return;
}
p = p.left;
}
}
}
/** * 二叉树删除
*/
public void delete(int value) {
//p 表示指向要删除的节点，初始化指向跟结点
TreeNode1 p = root;
//pp 表示指向p的父节点
TreeNode1 pp = null;
while (p != null && p.data != value) {
pp = p;
if (value > p.data) p = p.right;
else p = p.left;
}
//没有找到节点p
if (p == null) {
return;
}
//要删除的节点有两个子节点
if (p.left != null && p.right != null) {
TreeNode1 minP = p.right;
TreeNode1 minPP = p;
while (minP.left != null) {
minPP = minP;
minP = minP.left;
}
//值替换
p.data = minP.data;
//下面变为删除minP了
p = minP;
pp = minPP;
}
//删除结点是叶子节点或者仅有一个子节点
TreeNode1 child;
if (p.left != null) {
child = p.left;
} else if (p.right != null) {
child = p.right;
} else child = null;
//删除根结点
if (pp == null) root = child;
else if (pp.left == p) pp.left = child;
else pp.right = child;
}
/** * 查找二叉树---最小节点
*/
public TreeNode1 findMin() {
if (root == null) {
return null;
}
//一直往左找左节点
TreeNode1 node = root;
while (node.left != null) {
node = node.left;
}
return node;
}
/** * 查找二叉树---最大节点
*/
public TreeNode1 findMax() {
if (root == null) {
return null;
}
//一直往右找左节点
TreeNode1 node = root;
while (node.right != null) {
node = node.right;
}
return node;
}
/** * 层次遍历
*/
public void levelOrder(TreeNode1 root){
LinkedList<TreeNode1> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
root = queue.pop();
System.out.print(root.data+" ");
if(root.left!=null) queue.add(root.left);
if(root.right!=null) queue.add(root.right);
}
}
public static void main(String[] args) {
BinarySearchTree searchTree = new BinarySearchTree();
searchTree.buildTree();
System.out.println("层次遍历的结果：");
searchTree.levelOrder(searchTree.root);
System.out.println();
System.out.println(searchTree.find1(6));
searchTree.delete(8);
System.out.println("删除元素8层次遍历的结果：");
searchTree.levelOrder(searchTree.root);
System.out.println();
searchTree.insert(9);
System.out.println("插入元素9层次遍历的结果：");
searchTree.levelOrder(searchTree.root);
System.out.println();
System.out.println("最小节点："+searchTree.findMin());
System.out.println("最大节点："+searchTree.findMax());
}
}
AI助手
二叉排序树是一种基于键值大小进行有序存储的数据结构...它通过左小右大的原则实现高效的插入、删除和查找操作...这种数据结构特别适合用于需要频繁搜索操作的应用场景...其核心优势在于能够通过二分查找策略快速定位目标节点...
此方法是一种高效的数据结构设计，在计算机科学领域具有重要的应用价值