Java-数据结构之二叉树(二叉查找树)
二叉查找树介绍
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。
二叉排序树定义，一棵空树，或者是具有下列性质的二叉树：
- 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 左、右子树也分别为二叉排序树；
- 没有键值相等的结点(可以使用链表)。
二叉树是每个节点最多有两个子树的树结构。它有五种基本形态：
二叉查找树结构图
二叉搜索树接口操作说明
插入
先取根节点进行比较，如果该值小于存储值，则转向左子树；如果该值大于存储的值，则转向右子树。直到下一个节点为空时,那么就将新值插入, 如果发现新值和节点有重复情况,那么可以转换为链表.
普通插入方式:
节点有重复情况:
搜索
先取根节点，如果根节点就等于我们要查找的数据，那就返回。如果要查找的数据比根节点要小，那么就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。
遍历
遍历树是根据一种特定的顺序访问树的每一个节点。比较常用的有前序遍历，中序遍历和后序遍历。而二叉搜索树最常用的是中序遍历(有序)。
①、中序遍历:左子树——》根节点——》右子树
先遍历左子树、然后访问根节点，最后遍历右子树；并且在遍历左右子树的时候。仍然是先遍历左子树，然后访问根节点，最后遍历右子树。
②、前序遍历:根节点——》左子树——》右子树
先访问根节点，再遍历左子树，最后遍历右子树；并且在遍历左右子树时，仍需先访问根节点，然后遍历左子树，最后遍历右子树。
③、后序遍历:左子树——》右子树——》根节点
先遍历左子树，然后遍历右子树，最后访问根节点；同样，在遍历左右子树的时候同样要先遍历左子树，然后遍历右子树，最后访问根节点。
以上遍历方式称为深度优先遍历,而我们其实还有种遍历.叫做广度优先遍历方式,其原理就是使用队列的机制.
广度优先遍历原理就是一次遍历一层节点,从左到右
- 先将根节点放入队列
- 然后循环每次弹出队列中首个节点,添加到数组中
- 并且将当前节点的左右两个节点放入队列尾部中
删除
相比查找和插入操作，删除操作要繁琐的多的多。下面分三种情况进行讨论，当然最一开始的是先找到要删除的节点：
- 如果要删除的节点没有子节点，我们只需要将父节点指向要删除节点的指针置为 null。
- 如果要删除的节点只有一个子节点（左或者右），我们就可以将它的子节点更新为父节点。
- 如果要删除的节点有两个子节点。那么需要找到这个节点的右子树中的最小左节点，把它替换到要删除的节点位置上。此时，还需要删掉最小节点在原来的位置置为 null，如果最小左节点还有右子节点那么需要将右子节点替换最小左节点
- 以上删除时候都要考虑根节点被删除情况
最复杂的删除情况(下图是两种删除情况,根节点和其他节点):
最大节点、最小节点
最大节点:
寻找方式就是,向右一直找直到最后一个节点就是最大的元素
最小节点:
寻找方式就是,向左一直找直到最后一个节点就是最小的元素
二叉查找树的时间复杂度
针对同一组数据，可以构造出不同形态的二叉查找树。
比如: 图中就根据同一组数据构造出了不同形态的二叉查找树。显然，查找、插入、删除的时间复杂度跟二叉树数据的形态有关系。 具体地说，时间复杂度跟树高度有关系。
比如: 在最左边的那棵二叉查找树中查找数据时，相当于在链表中查找数据，时间复杂度为 O(n)；
比如: 在最右边的那棵二叉查找树查找时（完全二叉树的情况），时间复杂度是最小的，为 O(logn)。
★对于二叉查找树的时间复杂度为 O(logn) 理解方式，那就是二叉查找树查找的思想和二分查找的思想是类似的，都是每次查找之后取一半。因此，这两者的时间复杂度都是 O(logn)。
虽然二叉查找树的时间复杂度可以达到 O(logn)，但是一旦出现不平衡的情况就会退出的特别严重，可能退化为 O(n)。显然，不平衡的二叉查找树是我们不希望遇到的，我们希望在任何时候，都能保持二叉查找树的平衡。因此有了平衡二叉查找树，平衡二叉查找树的高度接近 logn。所以查找、删除、插入操作的时间复杂度也比较稳定，都是 O(logn)。
在平衡二叉查找树中，比较苛刻的有 AVL 树，不那么苛刻的有红黑树，而红黑树在生活中被用的更多(其他文章会讲这些内容的)。
以上所有案例的实现
注意: 以下部分工具类没有提供,但是看代码注解就知道啥意思了,核心代码都提供了,学数据结构,不是抄代码,因为数据结构会随着场景而改造的,不可能一套就能在很多地方通用的,而一般通用的都不会太好速度也不会太快的,有句叫物以稀为贵
接口
package com.tree.binarytree;
import java.util.List;
/** * @author huanmin */
public interface Tree<T> {
//查找指定节点
public T find(T key);
//查询全部 ,各种遍历方式
public List<T> findAll(int type);
//广度查询
List<T> breadthFindAll();
//插入新节点
public boolean insert(T data);
//查找最大值
public T findMax();
//查找最小值
public T findMin();
//删除节点
public boolean delete(T key);
//修改节点
public boolean update(T key);
//Other Method......
}节点
package com.tree.binarytree;
import java.lang.reflect.Field;
/** * @author huanmin */
public class Node<T> {
private T data; //节点数据
private Linked linked; //链表
private Node<T> leftChild; //左子节点的引用
private Node<T> rightChild; //右子节点的引用
public Node(T data) {
this.data = data;
}
public Node() {
}
public Linked getLinked() {
return linked;
}
public void setLinked(Linked linked) {
this.linked = linked;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node<T> getLeftChild() {
return leftChild;
}
public void setLeftChild(Node<T> leftChild) {
this.leftChild = leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
public void setRightChild(Node<T> rightChild) {
this.rightChild = rightChild;
}
//通过反射拿到对象内的id值 ,(不允许字符串类型 ,只能是数值类型,或者对象类型里有id字段)
public long getClassId() {
if (this.getData() instanceof Number) {
Number data = (Number) (this.getData());
return data.longValue();
}
long l = 0L;
try {
Class<?> aClass = this.getData().getClass();
Field field = aClass.getDeclaredField("id");
field.setAccessible(true);
l = (long) field.get(this.getData());
} catch (NoSuchFieldException | IllegalAccessException e) {
e.printStackTrace();
}
return l;
}
//当数据发生重复时候转换为链表
protected class Linked {
private T data; //当前
private Linked linked; //下一个
public Linked(T data, Linked linked) {
this.data = data;
this.linked = linked;
}
public Linked(T data) {
this.data = data;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Linked getLinked() {
return linked;
}
public void setLinked(Linked linked) {
this.linked = linked;
}
}
public void delete(Node<T> node) {
this.setData(null);
this.setLinked(null);
this.setRightChild(null);
this.setLeftChild(null);
node=null;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
'}';
}
}接口实现类
package com.tree.binarytree;
import com.objcopy.utils.ObjectCopyUtil;
import java.util.*;
/** * @author huanmin */
public class BinaryTree<T> implements Tree<T> {
//根节点
private Node<T> root;
public BinaryTree(List<T> list) {
for (T t : list) {
this.insert(t);
}
}
public BinaryTree() {
}
@Override
public T find(T key) {
Node<T> node1 = new Node<>(key);
return find(root,node1);
}
public T find( Node<T> node, Node<T> node1) {
//0. 当前节点等于查找的值
if (node.getClassId()==node1.getClassId()) {
return node.getData();
}
//1 .如果查找值的小于当前节点那么就往左找
if (node.getClassId()>node1.getClassId()) {
if (node.getLeftChild()!=null) {
return find(node.getLeftChild(),node1);
}
}
//2. 如果查找的值大于当前节点那么就往右找
if (node.getClassId()<node1.getClassId()) {
if (node.getRightChild() != null) {
return find(node.getRightChild(),node1);
}
}
//没有找到
return null;
}
//(深度优先遍历) type = 1前序遍历 2中序遍历(有序列表(小到大)) 3 后续遍历 ,4中序遍历(有序列表(大到小))
@Override
public List<T> findAll(int type) {
//1. 查找全部节点,遍历全部左树,和右树 ,以及链表(需要递归)
List<T> nodes = new ArrayList<>();
findAll(nodes, root,type);
return nodes;
}
// 用递归的方法
private void findAll(List<T> nodes, Node<T> node,int type) {
if (type==4) { //中序遍历(大到小)
if (node.getRightChild() != null) {
findAll(nodes, node.getRightChild(),type);
}
findAllAndLinked(nodes,node);
if (node.getLeftChild() != null) {
findAll(nodes, node.getLeftChild(),type);
}
return;
}
//保存当前节点值
if (type==1) { //前序遍历
findAllAndLinked(nodes,node);
}
//如果当前节点的子左节点不为空那么就往下递归
if (node.getLeftChild() != null) {
findAll(nodes, node.getLeftChild(),type);
}
if (type==2) { //中序遍历(小到大)
findAllAndLinked(nodes,node);
}
//如果当前节点的子右节点不为空那么就往下递归
if (node.getRightChild() != null) {
findAll(nodes, node.getRightChild(),type);
}
if (type==3) {//后序遍历
findAllAndLinked(nodes,node);
}
}
//广度优先遍历
@Override
public ArrayList<T>breadthFindAll() {
ArrayList<T> lists=new ArrayList<T>();
if(root==null)
return lists;
Queue<Node<T>> queue=new LinkedList<Node<T>>();
queue.offer(root);
while(!queue.isEmpty()){
Node<T> tree=queue.poll();
if (tree.getLeftChild() != null) {
queue.offer(tree.getLeftChild());
}
if (tree.getRightChild() != null) {
queue.offer(tree.getRightChild());
}
this.findAllAndLinked(lists,tree);
}
return lists;
}
private void findAllAndLinked(List<T> nodes,Node<T> node) {
//如果节点被删除那么跳过
if (node.getData()==null) {
return;
}
//保存当前节点值
nodes.add(node.getData());
//拿到链表的子链表
Node<T>.Linked linked = node.getLinked();
if (linked!=null) {
//因为当前链表值就是当前节点的值,所以不需要添加
linked=linked.getLinked();
}
//如果发现有链表那么,开启遍历链表
while (linked != null) {
//将子链表的值添加
nodes.add(linked.getData());
//获取子链表是否为空
Node<T>.Linked linked1 = linked.getLinked();
if (linked1 == null) {
break;
}
//将链表引用保存
linked = linked1;
}
}
@Override
public boolean insert(T data) {
//1.先判断是否是空树,如果是那么当前插入的值作为树根
if (root == null) {
root = new Node<>(data);
return true;
}
// 将值放入node节点中
Node<T> node = new Node<>(data);
//2.拿当前节点和值进行比较(小的找左,大的找右),直到找到最后节点为null结束 ,然后插入
//记录当前查找的节点,默认都是从根节点开始找
Node<T> current = root;
while (true) {
//1.1左树(比父节点小)
if (current.getClassId() > node.getClassId()) {
//获取左节点的值
Node<T> leftChild = current.getLeftChild();
//如果为空那么就找到最深处了,那么就可以添加值到左节点
if (leftChild == null) {
current.setLeftChild(node);
return true;
} else {
current = leftChild;
}
}
//1.2右树(比父节点大)
if (current.getClassId() < node.getClassId()) {
//获取右节点的值
Node<T> rightChild = current.getRightChild();
//如果为空那么就找到最深处了,那么就可以添加值到右节点
if (rightChild == null) {
current.setRightChild(node);
return true;
} else {
current = rightChild;
}
}
//1.3 节点相同 (转换链表)
if (current.getClassId() == node.getClassId()) {
if (current.getLinked() == null) {
//将链表初始化,把当前节点的值和要添加的值都放入链表中
Node<T>.Linked linked1 = new Node<T>().new Linked(node.getData());
Node<T>.Linked linked2 = new Node<T>().new Linked(current.getData(), linked1);
current.setLinked(linked2);
return true;
} else {
//获取当节点的链表
Node<T>.Linked linked = current.getLinked();
while (true) {
//拿到连表的子链
Node<T>.Linked linked1 = linked.getLinked();
//判断子链是否为空,如果为空那么将当前重复的值挂载到这里
if (linked1 == null) {
Node<T>.Linked linked2 = new Node<T>().new Linked(node.getData());
linked.setLinked(linked2);
return true;
} else {
//如果不为空,继续往链表的子链表深入
linked = linked1;
}
}
}
}
}
}
@Override
public T findMax() {
if (root == null) {
return null;
}
return findMax(root);
}
public T findMax(Node<T> node) {
//1.原理就是查询所有节点的左子节点,最小的左子节点就是最小值
if (node.getRightChild()==null) {
return node.getData();
}
return findMin(node.getRightChild());
}
@Override
public T findMin() {
if (root == null) {
return null;
}
return findMin(root);
}
public T findMin(Node<T> node) {
//1.原理就是查询所有节点的左子节点,最小的左子节点就是最小值
if (node.getLeftChild()==null) {
return node.getData();
}
return findMin(node.getLeftChild());
}
@Override
public boolean delete(T key) {
//0.先查询到这个节点,和这个节点的父节点 [0]父节点 ,[1]当前节点
Map<String, Object> map = this.deleteFind(key);
//没有这个要删除的节点
if (map==null) {
return false;
}
Node<T> parent =(Node<T>) map.get("parent");
Node<T> current =(Node<T>) map.get("current");
String direction =(String) map.get("direction");
//1.删除的元素没有子节点(左和右),那么直接删除当前节点
if (current.getLeftChild()==null&¤t.getRightChild()==null) {
//将对象引用设置为空,加快垃圾收集器去回收这个空对象
current.delete(current);//清空数据
return true;
}
//2.1删除的元素有左子节点,就将这个左子节点代替当前节点
if (current.getLeftChild()!=null&¤t.getRightChild()==null) {
//如果当前节点是在父节点的左边,那么就将当前节点的左子节点,覆盖当前节点的父节点的左子节点
if(direction.equals("centre")) {
root = current.getLeftChild();
}else if (direction.equals("left")) {
parent.setLeftChild(current.getLeftChild());
} else {
parent.setRightChild(current.getLeftChild());
}
return true;
}
//2.2删除的元素有右子节点,就将这个右子节点代替当前节点
if (current.getLeftChild()==null&¤t.getRightChild()!=null) {
//如果当前节点是在父节点的右边,那么就将当前节点的右子节点,覆盖当前节点的父节点的右子节点
if(direction.equals("centre")) {
root = current.getRightChild();
}else if (direction.equals("right")) {
parent.setRightChild(current.getRightChild());
} else {
parent.setLeftChild(current.getRightChild());
}
return true;
}
//3.删除的元素有(左右)子节点 ,那么需要找到被删除节点的右子节点中的最小左子节点,然后替换删除的节点(注意:需要考虑最小节点有右节点的情况)
if (current.getLeftChild()!=null&¤t.getRightChild()!=null) {
//3.1删除的元素右节点没有左节点的情况,将删除元素的右节点覆盖删除的节点,然后在将删除元素的左节点放入到删除元素的右节的左节点中
Node<T> rightChild = current.getRightChild();
if (rightChild.getLeftChild() == null&&direction.equals("centre")) {
rightChild.setLeftChild(root.getLeftChild());
root=rightChild;
return true;
} else if (rightChild.getLeftChild() == null) {
rightChild.setLeftChild(current.getLeftChild());
parent.setRightChild(rightChild);
return true;
}
//删除元素右节点的最小左节点的父节点
Node<T> minParentChild =current;
//删除元素右节点的最小左节点
Node<T> minChild =current.getRightChild();
//3.2删除的元素右节点有左节点的情况,查询当前被删除的节点的右子节点的最小左子节点
while (minChild.getLeftChild() != null) {
minParentChild=minChild; //父节点
minChild= minChild.getLeftChild(); //子节点
}
//3.3删除元素的右节点的最小左节点是否还存在右节点的情况 ,如果存在那么,就将右节点放入最小左节,然后将最小左节放入被删除的节点
//移动顺序(不要弄反了不然会有问题的): 最小左节点的右节点 -> 最小左节点 -> 被删除节点
if (minChild.getRightChild()!=null) {
minParentChild.setLeftChild(minChild.getRightChild());
}
//3.4节点不存在右节点情况,将找到的最小左节点覆盖删除的节点,并且删除原来节点的位置
if (minChild.getRightChild()==null) {
minParentChild.setLeftChild(null);
}
//3.5(3.3和3.4)复用代码
if (direction.equals("left")) {
parent.setLeftChild(minChild);
return true;
} else if (direction.equals("centre")) {
minChild.setLeftChild(root.getLeftChild());
minChild.setRightChild(root.getRightChild());
root=minChild;
return true;
} else {
parent.setRightChild(minChild);
return true;
}
}
return false;
}
@Override
public boolean update(T key) {
try {
T t = this.find(key);
if (t==null) {
return false;
}
//方式1: 使用对象copy(反射方式), 如果出现问题那么就换成BeanCopier或者BeanUtils
ObjectCopyUtil.copy(key,t);
//方式2:获取到修改的父节点,然后将需要修改的节点给覆盖了就行
return true;
} catch (Exception e) {
e.printStackTrace();
}
return false;
}
private Map<String,Object> deleteFind(T key) {
Map<String,Object> nodes=new HashMap<>();
Node<T> node1 = new Node<>(key);
nodes.put("parent",root);
nodes.put("direction","centre");
return deleteFind(nodes,root,node1);
}
private Map<String,Object> deleteFind(Map<String,Object> nodes, Node<T> node, Node<T> node1) {
//0. 当前节点等于查找的值
if (node.getClassId()==node1.getClassId()) {
nodes.put("current",node); //当前节点
return nodes;
}
//1 .如果查找值的小于当前节点那么就往左找
if (node.getClassId()>node1.getClassId()) {
nodes.put("parent",node);//记录父节点
nodes.put("direction","left");//记录当前节点属于父节点哪一个方向
if (node.getLeftChild()!=null) {
return deleteFind(nodes,node.getLeftChild(),node1);
}
}
//2. 如果查找的值大于当前节点那么就往右找
if (node.getClassId()<node1.getClassId()) {
nodes.put("parent",node);//记录父节点
nodes.put("direction","right");//记录当前节点属于父节点哪一个方向
if (node.getRightChild() != null) {
return deleteFind(nodes,node.getRightChild(),node1);
}
}
//没有找到
return null;
}
}部分测试
package com.tree.binarytree;
import com.arithmetic.utils.CodeStartAndStopTimeUtil;
import com.arithmetic.utils.datasource.entity.UserData;
import org.junit.Test;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.atomic.AtomicReference;
public class TestTree {
@Test
public void insertTree() {
List<UserData> list22 = new ArrayList<UserData>(1000001);
for (int i = 0; i < 1000001; i++) {
Random random = new Random();
int i1 = random.nextInt(1000001);
UserData build = UserData.builder().id(i1).age(i1).name("").build();
list22.add(build);
}
//执行时长：7506 毫秒.
AtomicReference<BinaryTree<UserData>> userDataBlockList1 = new AtomicReference<>();
CodeStartAndStopTimeUtil.creator(() -> {
userDataBlockList1.set(new BinaryTree<UserData>(list22));
});
//执行时长：0 毫秒.
CodeStartAndStopTimeUtil.creator(() -> {
UserData build = UserData.builder().id(1000000).age(1000000).name("").build();
System.out.println(userDataBlockList1.get().find(build));
});
//执行时长：30 毫秒.
CodeStartAndStopTimeUtil.creator(() -> {
UserData build = UserData.builder().id(1000000).age(1000000).name("").build();
userDataBlockList1.get().findAll(3); //有序集合
});
}
@Test
public void updateTree() {
BinaryTree<UserData> bt = new BinaryTree<UserData>();
UserData build2 = UserData.builder().id(4).age(4).name("").build();
bt.insert(build2);
UserData build5 = UserData.builder().id(5).age(5).name("").build();
bt.insert(build5);
UserData buildu = UserData.builder().id(4).age(6).name("6").build();
bt.update(buildu);
System.out.println(bt.find(buildu));
}
@Test
public void breadthFindAll() {
List<UserData> list22 = new ArrayList<UserData>(500);
for (int i = 0; i <500; i++) {
Random random = new Random();
int i1 = random.nextInt(500);
UserData build = UserData.builder().id(i1).age(i1).name("").build();
// UserData build = UserData.builder().id(i).age(i).name("").build();
list22.add(build);
; //有序集合
}
System.out.println(list22.size());
BinaryTree<UserData> userDataBinaryTree = new BinaryTree<>(list22);
System.out.println(userDataBinaryTree.breadthFindAll().size());
}
@Test
public void deleteTree1() {
//1.删除的元素没有子节点(左和右),那么直接删除当前节点
BinaryTree<UserData> bt = new BinaryTree<UserData>();
UserData build2 = UserData.builder().id(4).age(4).name("").build();
bt.insert(build2);
//[UserData(id=4, name=, age=4)]
System.out.println(bt.findAll(2));
UserData build11 = UserData.builder().id(4).age(21).name("").build();
bt.delete(build11);
//[]
System.out.println(bt.findAll(2));
}
@Test
public void deleteTree2() {
//2.删除的元素有左子节点,就将这个左子节点代替当前节点
BinaryTree<UserData> bt = new BinaryTree<UserData>();
UserData build2 = UserData.builder().id(4).age(4).name("").build();
bt.insert(build2);
UserData build4 = UserData.builder().id(3).age(3).name("").build();
bt.insert(build4);
//[UserData(id=3, name=, age=3), UserData(id=4, name=, age=4)]
System.out.println(bt.findAll(2));
UserData build11 = UserData.builder().id(4).age(21).name("").build();
bt.delete(build11);
//[UserData(id=3, name=, age=3)]
System.out.println(bt.findAll(2));
}
@Test
public void deleteTree3() {
//2.删除的元素有左子节点,就将这个左子节点代替当前节点
BinaryTree<UserData> bt = new BinaryTree<UserData>();
UserData build2 = UserData.builder().id(4).age(4).name("").build();
bt.insert(build2);
UserData build4 = UserData.builder().id(5).age(5).name("").build();
bt.insert(build4);
//[UserData(id=4, name=, age=4), UserData(id=5, name=, age=5)]
System.out.println(bt.findAll(2));
UserData build11 = UserData.builder().id(4).age(21).name("").build();
bt.delete(build11);
//[UserData(id=5, name=, age=5)]
System.out.println(bt.findAll(2));
}
@Test
public void deleteTree4() {
//3.删除的元素有(左右)子节点 ,那么需要找到被删除节点的右子节点中的最小左子节点,然后替换删除的节点(注意:需要考虑最小节点有右节点的情况)
//3.1删除的元素右节点没有左节点的情况,将删除元素的右节点覆盖删除的节点,然后在将删除元素的左节点放入到删除元素的右节的左节点中
BinaryTree<UserData> bt = new BinaryTree<UserData>();
UserData build2 = UserData.builder().id(4).age(4).name("").build();
bt.insert(build2);
UserData build4 = UserData.builder().id(5).age(5).name("").build();
bt.insert(build4);
UserData build41 = UserData.builder().id(6).age(6).name("").build();
bt.insert(build41);
UserData build3 = UserData.builder().id(3).age(3).name("").build();
bt.insert(build3);
//[UserData(id=4, name=, age=4), UserData(id=5, name=, age=5)]
System.out.println(bt.findAll(2));
UserData build11 = UserData.builder().id(4).age(21).name("").build();
bt.delete(build11);
//[UserData(id=5, name=, age=5)]
System.out.println(bt.findAll(2));
}
@Test
public void deleteTree5() {
//3.删除的元素有(左右)子节点 ,那么需要找到被删除节点的右子节点中的最小左子节点,然后替换删除的节点(注意:需要考虑最小节点有右节点的情况)
//3.3删除元素的右节点的最小左节点是否还存在右节点的情况 ,如果存在那么,就将右节点放入最小左节,然后将最小左节放入被删除的节点
BinaryTree<UserData> bt = new BinaryTree<UserData>();
UserData build2 = UserData.builder().id(4).age(4).name("").build();
bt.insert(build2);
UserData build3 = UserData.builder().id(3).age(3).name("").build();
bt.insert(build3);
UserData build8 = UserData.builder().id(8).age(8).name("").build();
bt.insert(build8);
UserData build41 = UserData.builder().id(5).age(5).name("").build();
bt.insert(build41);
UserData build6 = UserData.builder().id(6).age(6).name("").build();
bt.insert(build6);
UserData build11 = UserData.builder().id(10).age(10).name("").build();
bt.insert(build11);
UserData build22 = UserData.builder().id(13).age(13).name("").build();
bt.insert(build22);
//[UserData(id=4, name=, age=4), UserData(id=5, name=, age=5)]
System.out.println(bt.findAll(2));
UserData build1111 = UserData.builder().id(4).age(21).name("").build();
bt.delete(build1111);
//[UserData(id=5, name=, age=5)]
System.out.println(bt.findAll(2));
}
@Test
public void deleteTree6() {
//3.删除的元素有(左右)子节点 ,那么需要找到被删除节点的右子节点中的最小左子节点,然后替换删除的节点(注意:需要考虑最小节点有右节点的情况)
//3.4节点不存在右节点情况,将找到的最小左节点覆盖删除的节点,并且删除原来节点的位置
BinaryTree<UserData> bt = new BinaryTree<UserData>();
UserData build2 = UserData.builder().id(4).age(4).name("").build();
bt.insert(build2);
UserData build4 = UserData.builder().id(8).age(8).name("").build();
bt.insert(build4);
UserData build6 = UserData.builder().id(6).age(6).name("").build();
bt.insert(build6);
UserData build11 = UserData.builder().id(10).age(10).name("").build();
bt.insert(build11);
UserData build22 = UserData.builder().id(13).age(13).name("").build();
bt.insert(build22);
UserData build3 = UserData.builder().id(3).age(3).name("").build();
bt.insert(build3);
//[UserData(id=4, name=, age=4), UserData(id=5, name=, age=5)]
System.out.println(bt.findAll(2));
UserData build1111 = UserData.builder().id(4).age(21).name("").build();
bt.delete(build1111);
//[UserData(id=5, name=, age=5)]
System.out.println(bt.findAll(2));
}
}点赞 -收藏-关注-便于以后复习和收到最新内容有其他问题在评论区讨论-或者私信我-收到会在第一时间回复如有侵权，请私信联系我感谢,配合,希望我的努力对你有帮助^_^
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/weixin_45203607/article/details/122241476
内容来源于网络，如有侵权，请联系作者删除！