当前位置：网站首页>（十三）二叉排序树
（十三）二叉排序树
2022-08-04 05:28:00 【顺毛黑起】
基本概念
二叉排序树：BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。
特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点
创建和遍历
package com.atguigu.binarysorttree;
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]));
}
System.out.println("中序遍历二叉排序树~~~");
binarySortTree.infixOrder();
}
}
//创建二叉排序树
class BinarySortTree{
private Node root;
//添加结点的方法
public void add(Node node){
if (root==null){
root=node;//如果root为空则直接让root指向node
}else {
root.add(node);
}
}
//中序遍历
public void infixOrder(){
if (root !=null){
root.infixOrder();
}else {
System.out.println("二叉排序树为空，不能遍历~~~");
}
}
}
//创建Node结点
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){
//如果当前结点的左子结点为空
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();
}
}
}
删除结点
二叉排序树的删除情况比较复杂，有下面三种情况需要考虑
- 删除叶子节点 (比如：2, 5, 9, 12)
- 删除只有一颗子树的节点 (比如：1)
- 删除有两颗子树的节点. (比如：7, 3，10 )
第一种情况 删除叶子节点 (比如：2, 5, 9, 12)
思路
(1) 需求先去找到要删除的结点 targetNode
(2) 找到 targetNode 的 父结点 parent
(3) 确定 targetNode 是 parent 的左子结点 还是右子结点
(4) 根据前面的情况来对应删除
- 左子结点 parent.left = null
右子结点 parent.right = null;
第二种情况: 删除只有一棵子树的结点 （比如1）
思路
(1) 需求先去找到要删除的结点 targetNode
(2) 找到 targetNode 的 父结点 parent
(3) 确定 targetNode 的子结点是左子结点还是右子结点
(4) targetNode 是 parent 的左子结点还是右子结点
(5) 如果 targetNode 有左子结点
5. 1 如果 targetNode 是 parent 的左子结点
parent.left = targetNode.left;
5.2 如果 targetNode 是 parent 的右子结点
parent.right = targetNode.left;
(6) 如果 targetNode 有右子结点
6.1 如果 targetNode 是 parent 的左子结点
parent.left = targetNode.right;
6.2 如果 targetNode 是 parent 的右子结点
parent.right = targetNode.right
情况三 ： 删除有两棵子树的结点. (比如10)
思路
(1) 需求先去找到要删除的结点 targetNode
(2) 找到 targetNode 的 父结点 parent
(3) 从 targetNode 的右子树找到最小的结点(或者左子树的最大的结点)
(4) 用一个临时变量，将 最小结点的值保存 temp = 12
(5) 删除该最小结点
(6) targetNode.value = temp
package com.atguigu.binarysorttree;
public class BinarySortTreeDemo {
public static void main(String[] args) {
int[] arr={
7,3,10,12,5,1,9,2};
BinarySortTree binarySortTree = new BinarySortTree();
//循环的添加结点到二叉排序树
for (int i = 0; i < arr.length; i++) {
binarySortTree.add(new Node(arr[i]));
}
System.out.println("中序遍历二叉排序树~~~");
binarySortTree.infixOrder();
//删除叶子结点
// binarySortTree.delNoode(2);
// System.out.println("删除结点后");
// binarySortTree.infixOrder();
//删除只有一棵子树的结点
// binarySortTree.delNoode(1);
// System.out.println("删除结点后");
// binarySortTree.infixOrder();
//删除有两棵子树的结点
binarySortTree.delNoode(7);
System.out.println("删除结点后");
binarySortTree.infixOrder();
}
}
//创建二叉排序树
class BinarySortTree{
private Node root;
//查找要删除的结点
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);
}
}
//
/** * 1.返回以node为根结点的二叉排序树的最小结点的值 * 2.删除node为根结点的二叉排序树的最小结点 * @param node 传入的结点（以该结点为根结点的二叉排序树（整个二叉排序树的子树）） * @return 返回以node为根结点的二叉排序树的最小结点的值 */
public int delRightTreeMin(Node node){
Node target=node;
//循环的查找左结点，就会找到最小值
while (target.left!=null){
target=target.left;
}
//这时，target就指向了最小的结点
//删除最小结点
delNoode(target.value);
return target.value;
}
//删除结点
public void delNoode(int value){
if (root==null){
return;
}else {
//(1) 需求先去找到要删除的结点 targetNode
Node targetNode = search(value);
//如果没找到要删除的结点
if (targetNode==null){
return;
}
//如果发现当前这棵二叉排序树只有一个结点
if (root.left==null && root.right==null){
root=null;
return;
}
//找到targetNode的父结点
Node parent=searchParent(value);
//如果要删除的结点是叶子结点
if (targetNode.left==null && targetNode.right==null){
if (parent.left!=null && parent.left.value==value){
parent.left=null;
}else if (parent.right!=null && parent.right.value==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 {
root=targetNode.right;
}
}
}
}
}
//添加结点的方法
public void add(Node node){
if (root==null){
root=node;//如果root为空则直接让root指向node
}else {
root.add(node);
}
}
//中序遍历
public void infixOrder(){
if (root !=null){
root.infixOrder();
}else {
System.out.println("二叉排序树为空，不能遍历~~~");
}
}
}
//创建Node结点
class Node{
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
//查找要删除的结点
public Node search(int value){
//这里不需要判断是否为空，因为在这里调用search的一定是当前结点，所以一定不为空
if(value==this.value){
return this;
}else if (value<this.value){
//如果查找的值小于当前结点，向左子树递归查找
if (this.left==null) {
//如果左子结点为空
return null;
}
return this.left.search(value);
}else {
//如果查找的值大于当前结点，向右子树递归查找
if (this.right==null) {
//如果右子结点为空
return null;
}
return this.right.search(value);
}
}
//查找要删除结点的父结点
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;//没有找到父结点
}
}
}
//添加结点的方法
//递归的添加结点，需要满足二叉排序树的要求
public void add(Node node){
if (node==null){
return;
}
//判断传入的结点的值，和当前子树的根结点的关系
if (node.value<this.value){
//如果当前结点的左子结点为空
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();
}
}
}
边栏推荐
猜你喜欢
随机推荐
flink-sql查询配置与性能优化参数详解
页面刷新没有执行watch？
win云服务器搭建个人博客失败记录（wordpress，wamp）
MySQL事务详解(事务隔离级别、实现、MVCC、幻读问题)
实现登录密码混合动态因子，且动态因子隐式
实际开发中，客户要求密码输入框禁止粘贴~
二月、三月校招面试复盘总结（二）
对象存储-分布式文件系统-MinIO-1：概念
大龄程序员的心理建设
SQL练习 2022/7/1
自己学习爬虫写的基础小函数
箭头函数的使用
JS原型链
[原创]STL容器map和unordered_map性能，创建，插入，随机访问速度对比！
JS代码预编译
CTFshow—Web入门—信息（1-8）
程序员也应了解的Unity粒子系统
SQL练习 2022/7/2
字符串常用方法
Kubernetes基本入门-集群资源（二）