先上部分理论（难点），再上代码
1.创建二叉搜索树
解法1：（不是最优的，得到的是非平衡二叉树）
image.png
image.png
解法2：（最优，得到的是平衡二叉树）
首先对序列进行排序，得26,28,35,38,50,55,62,94，每次从中点处开始构建
image.png
2.删除节点
image.png
image.png
删除双支节点：
image.png
为了更好理解，说明如下（参考https://blog.csdn.net/isea533/article/details/80345507）：
image.png
当我们删除 30 节点的时候，整个中序遍历的结果中，从 32 开始都往前移动了一位。32 是 30 的后继节点，就是比 30 大的节点中最小的节点。当某个节点存在右节点时，后继结点就是右节点中的最小值，由于左侧节点总比右侧节点和父节点小，所以后继节点一定没有左节点。从这一个特点就能看出来，后继结点有可能存在右节点，也有可能没有任何节点。后继结点还有一个特点，就是他比 30 的左节点大，比 30 所有的右节点都小，因此删除 30 的时候，可以直接将后继结点 32 的值（key）转移到 30 节点上，然后删除后继结点 32。由于后继结点最多只有一个子节点，因此删除后继节点时，就变成了 3 种情况中的前两种。图示如下：
image.png
上图意思是用当前节点的右孩子中最小的一个节点替换掉当前节点，再删除右孩子中最小的节点即可；同理，可用当前节点的左孩子中最大的节点替换掉当前节点，再删除左孩子中最大的节点即可（见方法二），本节使用方法二实现，不使用上图进行实现，但是原理一样
public interface BinarySerachTreeInterface {
/**
* 创建非平衡的二叉搜索树
* @param arr
* @return
*/
TreeNode createNonBalanceBinarySerachTree(int[] arr);
/**
* 创建平衡的二叉搜索树
* @param arr
* @return
*/
TreeNode createBalanceBinarySerachTree(int[] arr);
/**
* 在root中插入节点node
* @param root
* @param node
*/
TreeNode insertTreeNode(TreeNode root,TreeNode node);
/**
* 在root中查找值为value的结点，
* 若存在该结点 则return true 否则 return false
* @param root
* @param value
* @return
*/
boolean selectTreeNode(TreeNode root,int value);
/**
* 分三种情况：删除叶子节点、删除单支节点和删除双支节点
* @param node
* @return
*/
boolean deleteTreeNode(TreeNode node);
/**
* 在root中将第一个出现的oldValue更新为newValue
* 存在一个问题，就是更新之后，可能就不是二叉查找树了
* 因此，一般的用法是：例如根据学号找到某个学生，然后更新学生的成绩信息
* @param root
* @param oldValue
* @param newValue
* @return
*/
boolean updateTreeNode(TreeNode root,int oldValue,int newValue);
}
import java.util.Arrays;
public class BinarySerachTreeImpl implements BinarySerachTreeInterface {
/**
* 头结点
*/
TreeNode head;
@Override
public TreeNode createNonBalanceBinarySerachTree(int[] arr) {
if(arr.length==0)
return head;
head=new TreeNode(arr[0]);
TreeNode currentNode;
for (int i=1;i<arr.length;i++){
//每次都从头开始插入
currentNode=head;
while (currentNode != null){
if(currentNode.getData()>arr[i]){
//挂在currentNode的左孩子上
if(currentNode.getLeft()==null){
currentNode.setLeft(new TreeNode(arr[i]));
break;
}else {
currentNode=currentNode.getLeft();
}
}else {
//挂在currentNode的右孩子上
if(currentNode.getRight()==null){
currentNode.setRight(new TreeNode(arr[i]));
break;
}else {
currentNode=currentNode.getRight();
}
}
}
}
return head;
}
/**
*
* @param arr 前提是数组有序
* @return
*/
@Override
public TreeNode createBalanceBinarySerachTree(int[] arr) {
//升序
Arrays.sort(arr);
return balanceBTree(arr,0,arr.length-1);
}
private TreeNode balanceBTree(int[] arr, int start, int end) {
if(start>end)
return null;
//取中点
int mid=start+((end-start)>>1);
TreeNode root=new TreeNode(arr[mid]);
root.setLeft(balanceBTree(arr,start,mid-1));
root.setRight(balanceBTree(arr,mid+1,end));
return root;
}
/**
* createNonBalanceBinarySerachTree 的一部分
* @param root
* @param node
* @return
*/
@Override
public TreeNode insertTreeNode(TreeNode root,TreeNode node) {
if(root==null)
root = node;
TreeNode currentNode=root;
while (currentNode != null){
if(currentNode.getData()>node.getData()){
//挂在currentNode的左孩子上
if(currentNode.getLeft()==null){
currentNode.setLeft(node);
break;
}else {
currentNode=currentNode.getLeft();
}
}else {
//挂在currentNode的右孩子上
if(currentNode.getRight()==null){
currentNode.setRight(node);
break;
}else {
currentNode=currentNode.getRight();
}
}
}
return root;
}
@Override
public boolean selectTreeNode(TreeNode root,int value) {
TreeNode currentNode=root;
while (currentNode!=null){
if(currentNode.getData()>value){
//在左孩子上找
currentNode=currentNode.getLeft();
}else if(currentNode.getData()<value){
//在右孩子上找
currentNode=currentNode.getRight();
}else {
return true;
}
}
return false;
}
/**
* 分三种情况：删除叶子节点、删除单支节点和删除双支节点
* @param root
* @param value
* @return
*/
@Override
public TreeNode deleteTreeNode(TreeNode root,int value) {
TreeNode currentNode=root;
//当前节点的父节点，作用是用于删除叶子节点
TreeNode parent=currentNode;
//用于标记currentNode是parent的左孩子还是右孩子
int flag=0;
while (currentNode!=null){
if(currentNode.getData()>value){
//左孩子
parent=currentNode;
flag=-1;
currentNode=currentNode.getLeft();
}else if(currentNode.getData()<value){
//右孩子
parent=currentNode;
flag=1;
currentNode=currentNode.getRight();
}else {
/**
* 节点值存在
*/
if(currentNode.getLeft()==null || currentNode.getRight()==null){
if(currentNode.getLeft()==null && currentNode.getRight()==null){
//删除叶子节点
if(flag==-1)
//currentNode是parent的左孩子
parent.setLeft(null);
if (flag==1)
//currentNode是parent的右孩子
parent.setRight(null);
break;
/**这么写的话是一颗空树，并没有删除
currentNode.setData(null);
currentNode.setLeft(currentNode.getLeft());
currentNode.setRight(currentNode.getRight());
*/
/**
* currentNode=null;也不行，原因可能涉及引用传递和值传递问题
*/
}else {
//删除单支节点（只需把下一个节点的值复制到当前节点，
// 然后当前节点指向下下个左右孩子节点即可）
//左孩子
TreeNode leftChild;
//右孩子
TreeNode rightChild;
if (currentNode.getLeft()==null){
//左子树为空
rightChild=currentNode.getRight();
//把下一个节点的值复制到当前节点
currentNode.setData(rightChild.getData());
// 当前节点指向下下个左右孩子节点
currentNode.setLeft(rightChild.getLeft());
currentNode.setRight(rightChild.getRight());
break;
}else {
//右子树为空
leftChild=currentNode.getLeft();
//把下一个节点的值复制到当前节点
currentNode.setData(leftChild.getData());
// 当前节点指向下下个左右孩子节点
currentNode.setLeft(leftChild.getLeft());
currentNode.setRight(leftChild.getRight());
break;
}
}
}else {
//删除双支节点
//找要删除节点的前驱节点（前驱节点是当前节点的左子树中值最大的，
// 前驱节点右子树必为null）
//从当前节点的左子树中开始寻找
TreeNode preNode=currentNode.getLeft();
//标记preNode是左孩子
flag=-1;
while (preNode.getRight() != null){
//标记preNode是右孩子
if(flag!=1)
flag=1;
parent=preNode;
preNode=preNode.getRight();
}
//前驱结点(preNode)的位置，将前驱结点的值复制到当前节点中
currentNode.setData(preNode.getData());
TreeNode preNodeLeft;
//删除前驱结点
if((preNodeLeft=preNode.getLeft())!=null){
//前驱节点有左孩子,即preNode.getLeft()！= null
//（即删除单支节点思想，因为前驱结点的右子树必为null）
preNode.setData(preNodeLeft.getData());
preNode.setLeft(preNodeLeft.getLeft());
preNode.setRight(preNodeLeft.getRight());
break;
}else {
//前驱节点没有左孩子，即它是叶子节点
if(flag==-1)
parent.setLeft(null);
if(flag==1)
parent.setRight(null);
break;
}
}
}
}
return root;
}
/**
* 存在一个问题，就是更新之后，可能就不是二叉查找树了
* 因此，一般的用法是：例如根据学号找到某个学生，然后更新学生的成绩信息
* @param root
* @param oldValue
* @param newValue
* @return
*/
@Override
public boolean updateTreeNode(TreeNode root,int oldValue,int newValue) {
TreeNode currentNode=root;
while (currentNode!=null){
if(currentNode.getData()>oldValue){
//左孩子
currentNode=currentNode.getLeft();
}else if(currentNode.getData()< oldValue){
//右孩子
currentNode=currentNode.getRight();
}else {
currentNode.setData(newValue);
return true;
}
}
return false;
}
//BTreeOpration 实现：https://www.jianshu.com/writer#/notebooks/45706548/notes/69590811/preview
public static void main(String[] args){
BinarySerachTreeImpl b=new BinarySerachTreeImpl();
BTreeOpration bTreeOpration=new BTreeOpration();
// TreeNode balanceTree=b.createBalanceBinarySerachTree(new int[]{38,26,62,35,50,94,28,55});
// bTreeOpration.inOrderTraverseBTree(balanceTree);
// System.out.println();
//创建非平衡二叉搜索树
TreeNode nonBalanceTree=b.createNonBalanceBinarySerachTree(new int[]{38,26,62,35,50,94,28,55});
bTreeOpration.inOrderTraverseBTree(nonBalanceTree);
System.out.println();
//向非平衡二叉搜索树中插入结点
TreeNode node=b.insertTreeNode(nonBalanceTree,new TreeNode(25));
bTreeOpration.inOrderTraverseBTreeIterator(node);
//在非平衡二叉搜索树中查询某结点
boolean isFind=b.selectTreeNode(node,50);
System.out.println(isFind);
boolean isUpdate=b.updateTreeNode(node,94,24);
System.out.println(isUpdate);
//在非平衡二叉搜索树中删除某结点
b.deleteTreeNode(nonBalanceTree,62);
bTreeOpration.inOrderTraverseBTreeIterator(nonBalanceTree);
}
}
/**
* 二叉树结点
*/
public class TreeNode {
private TreeNode left;
private TreeNode right;
private int data;
/**
* 构造节点
* @param data
*/
public TreeNode(int data) {
this.data = data;
this.left=null;
this.right=null;
}
public TreeNode(){}
public void setLeft(TreeNode left) {
this.left = left;
}
public void setRight(TreeNode right) {
this.right = right;
}
public Integer getData() {
return data;
}
public TreeNode getLeft() {
return left;
}
public TreeNode getRight() {
return right;
}
public void setData(int data) {
this.data = data;
}
@Override
public String toString() {
return "TreeNode{" +
"left=" + left +
", right=" + right +
", data=" + data +
'}';
}
}
