二叉排序树
- Binary Sort Tree,简称BST，要求二叉排序树的任意一个非叶子节点的左节点的值<=该节点值<=右节点值
1.0 二叉排序树的创建和遍历思路分析
- 节点类
- 属性：value,left,right
- 构造器：this.value=value
- 添加节点方法：给定一个需要新节点，以递归方式添加
- 中序遍历方法
- 二叉排序树类
- 添加方法+遍历方法
- 代码
package com.guodaxia.threadedbinarytree;
/**
* 二叉排序树
* @ author Guo daXia
* @ create 2022/11/29
*/
public class BinarySortTreeDemo {
public static void main(String[] args) {
int[] arr={7,3,10,12,5,1,9};
BinarySortTree binarySortTree = new BinarySortTree();
//循环的添加节点到
for (int i=0;i<arr.length;i++){
binarySortTree.add(new Node(arr[i]));
}
//中序遍历二叉排序树
binarySortTree.infixOrder();
}
}
//创建二叉排序树
class BinarySortTree{
private Node root;
//方法：添加节点
public void add(Node node){
if (root==null){
root = node;//如果root为空
}else {
root.add(node);
}
}
//中序遍历
public void infixOrder(){
if (root!=null){
root.infixOrder();
}else {
System.out.println("当前二叉树为空！");
}
}
}
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
//方法：添加节点
public void add(Node node){
if (node==null){
return;
}
//新节点值小于当前节点值，
if (node.value<this.value){
//如果当前节点左子节点为null
if (this.left==null){
this.left=node;
}else {
//否则，向左递归
this.left.add(node);
}
}else {
//如果大于当前节点
if (this.right==null){
this.right=node;
}else {
//向右递归
this.right.add(node);
}
}
}
//中序遍历
public void infixOrder(){
if (this.left!=null){
this.left.infixOrder();
}
System.out.println(this);
if (this.right!=null){
this.right.infixOrder();
}
}
}
- 输出：
Node{value=1}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}
- 总结：
- 插入一个元素快，因为采用了链式方法
- 查找一个元素快，类似于二分查找法
- 二叉排序树的添加方法和遍历方法的具体实现，交代给节点类思考如何实现，而二叉排序树只需要简单的判断怎么调用
2.0 二叉排序树的删除
-
分析:分为三种情况
- 删除叶子节点，如上图右边的元素（2，5，9，12）
- 删除只有一颗子树的节点，如元素（1）
- 删除有两颗子树的节点，如元素（7，3，10）
- 对删除节点的各种情况的思路分析：
-
删除叶子节点
思路：
- 先找到要删除的节点 targetNode
- 再找到targetNode的父节点 parent
- 确定两者位置关系：
- 如果targetNode是parent的左子节点，则parent.left=null;
- 如果targetNode是parent的右子节点，则parent.right=null;
-
删除只有一颗子树的节点
思路：
-
先找到要删除的节点 targetNode
-
再找到targetNode的父节点 parent
-
确定两者位置关系：
-
要删除的目标节点targetNode只有左子树，且targetNode是父节点parent的左子节点：
parent.left = targetNode.left;\ -
要删除的目标节点targetNode只有左子树，且targetNode是父节点parent的右子节点：
parent.right = targetNode.left; -
要删除的目标节点targetNode只有右子树，且targetNode是父节点parent的左子节点:
parent.left = targetNode.right; -
要删除的目标节点targetNode只有右子树，且targetNode是父节点parent的右子节点：
parent.right = targetNode.right;
-
-
-
删除有两颗子树的节点
思路：
- 先找到要删除的节点 targetNode
- 再找到targetNode的父节点 parent
- 从targetNode 的右子树找到最小的节点
- 用一个临时变量保存最小节点的值 temp
- 删除该最小节点
targetNode.value = temp;用temp值进行覆盖要删除节点的值
-
代码实现：
package binarysorttree;
public class Node {
int value;
Node left;
Node right;
public Node() {
}
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
//方法：添加节点
public void add(Node node) {
if (node == null) {
return;
}
//新节点值小于当前节点值，
if (node.value < this.value) {
//如果当前节点左子节点为null
if (this.left == null) {
this.left = node;
} else {
//否则，向左递归
this.left.add(node);
}
} else {
//如果大于当前节点
if (this.right == null) {
this.right = node;
} else {
//向右递归
this.right.add(node);
}
}
}
//中序遍历
public void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.infixOrder();
}
}
//方法：查找指定待删节点的值
public Node search(int value) {
//如果要删节点恰好为当前节点
if (value == this.value) {
return this;
} else if (value < this.value) {
//如果待删节点的值小于当前节点，向左递归查找
//如果左节点为空，则直接返回null
if (this.left == null) {
return null;
}
return this.left.search(value);
} else {
//如果待删节点的值大于当前节点，向右递归查找
if (this.right == null) {
return null;
}
return this.right.search(value);
}
}
/**
* 方法：查找指定待删节点的父节点
*
* @param value 为待删节点的值
* @return 返回的是要删除节点的父节点，如果没有，则返回null
*/
public Node searchParent(int value) {
//如果当前节点就是要删除的节点的父节点，直接返回
if (this.left != null && this.left.value == value
|| this.right != null && this.right.value == value) {
return this;
} else {
//如果查找的值小于当前节点的值，且当前节点的左子节点不为空
if (value < this.value && this.left != null) {
//向左子树递归查找
return this.left.searchParent(value);
} else if (value >= this.value && this.right != null) {
//如果查找的值大于等于当前节点的值，且右子树不为空
//向右子树递归查找
return this.right.searchParent(value);
} else {
//从二叉排序树中无法找到待删节点的父节点
return null;
}
}
}
}
package binarysorttree;
//创建二叉排序树
public class BinarySortTree {
private Node root;
public Node getRoot() {
return root;
}
//方法：添加节点
public void add(Node node) {
if (root == null) {
root = node;//如果root为空
} else {
root.add(node);
}
}
//中序遍历
public void infixOrder() {
if (root != null) {
root.infixOrder();
} else {
System.out.println("当前二叉树为空！");
}
}
//方法：删除节点
public void delNode(int value) {
if (root == null) {
return;
} else {
//1. 先找到要删除的节点 targetNode
Node targetNode = search(value);
//如果没有找到要删除的节点
if (targetNode == null) {
return;
}
//如果发现当前这颗二叉排序树只有一个节点，即只有root
if (root.left == null && root.right == null) {
//先置空root节点
root = null;
return;
}
//2. 再找到targetNode的父节点 parents
Node parent = searchParent(value);
//如果待删除的节点 是 叶子节点
if (targetNode.left == null && targetNode.right == null) {
//判断该叶子节点是父节点parent的左子节点还是右子节点
if (parent.left != null && parent.left.value == targetNode.value) {
parent.left = null;
} else if (parent.right != null && parent.right.value == targetNode.value) {
parent.right = null;
}
} else if (targetNode.left != null && targetNode.right != null) {//删除有两颗子树的节点
//用一个临时变量存待删节点的右子树中数据最小的值
int minVal = delRightTreeMin(targetNode.right);
//修改待删节点的值，完成删除
targetNode.value = minVal;
} else {//删除只有一颗子树的节点
//如果要删除的节点有左子节点
if (targetNode.left != null) {
if (parent != null) {
//如果targetNode 是parent的左子节点
if (parent.left.value == value) {
parent.left = targetNode.left;
} else {//targetNode 是parent的右子节点
parent.right = targetNode.left;
}
} else {//
root = targetNode.left;
}
} else {//如果要删除的节点有右子节点
if (parent != null) {
//如果targetNode 是parent的左子节点
if (parent.left.value == value) {
parent.left = targetNode.right;
} else {//targetNode 是parent的右子节点
parent.right = targetNode.right;
}
} else {//parent为空
root = targetNode.right;
}
}
}
}
}
/**
* 找寻 待删节点的右子树中 数 最小的值
* @param node 给一个节点:待删节点的右子节点
* @return 返回的是 以 node为根节点的二叉排序树的最小节点的值
*/
private int delRightTreeMin(Node node){
Node target = node;
//循环找到右子树中的最小值
while (target.left != null) {//在待删节点的右子树中，向左边找
target = target.left;
}
//找到了后，先删除最小节点
delNode(target.value);
//再将该最小节点给临时变量
return target.value;
}
//方法：查找要删除的节点
public Node search(int value){
if (root == null) {
return null;
} else {
return root.search(value);
}
}
//方法：查找父节点
public Node searchParent ( int value){
if (root == null) {
return null;
} else {
return root.searchParent(value);
}
}
}
package binarysorttree;
/**
* 二叉排序树
* @ author Guo daXia
* @ create 2022/11/29
*/
public class BinarySortTreeDemo {
public static void main(String[] args) {
int[] arr={7,3,10,12,5,1,9};
BinarySortTree binarySortTree = new BinarySortTree();
//循环的添加节点到二叉树里
for (int i=0;i<arr.length;i++){
binarySortTree.add(new Node(arr[i]));
}
//中序遍历二叉排序树
binarySortTree.infixOrder();
//测试删除叶子节点
//binarySortTree.delNode(12);
//输出
System.out.println("删除节点后");
binarySortTree.infixOrder();
//测试删除只有两颗子树的节点
binarySortTree.delNode(7);
System.out.println("删除节点后");
binarySortTree.infixOrder();
//测试删除只有一颗子树的节点
binarySortTree.delNode(10);
System.out.println("删除节点后");
binarySortTree.infixOrder();
}
}
- 后台测试
Node{value=1}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}
删除节点后
Node{value=1}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}
删除节点后
Node{value=1}
Node{value=3}
Node{value=5}
Node{value=9}
Node{value=10}
Node{value=12}
删除节点后
Node{value=1}
Node{value=3}
Node{value=5}
Node{value=9}
Node{value=12}
- 总结
- 将具体逻辑实现基本操作用方法封装在Node类里，如二叉排序树的添加、遍历、删除
- 在二叉排序树类里，是实际上要对这颗树进行添加、遍历、删除，也就是我们表面上看到的操作
- 在删除节点分为三种情况，需要掌握