二叉排序树
BST: (Binary Sort(Search) Tree),对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。
特别说明:如果有相同的值，可以将该节点放在左子节点或右子节点
比如针对数据(7,3, 10,12.5,1,9) 。一个数组创建成对应的二叉排序树，并使用中序遍历二叉排序树，比如: 数组为Array(7,3, 10, 12,5,1, 9，5)，创建成对应的二叉排序树为:
删除
二叉排序树的删除情况比较复杂，有下面三种情况需要考虑
1)删除叶子节点(比如: 2,5, 9, 12)
2)删除只有一颗子树的节点(比如: 1)
3)删除有两颗子树的节点. (比如: 7,3，10 )
第一种情况:
删除叶子节点(比如: 2,5, 9, 12)
思路
(1)需求先去找到要删除的结点targetNode
(2)找到targetNode的父结点parent
(3)确定targetNode是parent的左子结点还是右子结点
(4)根据前面的情况来对应删除
左子结点parent.left = null
右子结点parent.right = null;
第二种情况:删除只有一颗子树的节点 比如
思路
(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
情况三:删除有两颗子树的节点. (比如: 7,3 10)
思路
(1)需求先去找到要删除的结意targetNode
(2)找到targetNode 的父结点parent
(3)从targetNode的右子树找到最小的结点
(4)用一个临时变量，将最小结点的值保存temp
(5) 删除该最小結点
(6) targetNode.value = temp
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.delNode(2);
binarySortTree.delNode(3);
binarySortTree.delNode(7);
binarySortTree.delNode(5);
binarySortTree.delNode(9);
binarySortTree.delNode(12);
binarySortTree.delNode(10);
binarySortTree.delNode(1);
System.out.println("==");
binarySortTree.infixOrder();
}
}
//创建二叉排序树
class BinarySortTree{
private Node root;
//添加节点
public void add(Node node) {
if(root == null) {
root = node;
}else {
root.add(node);
}
}
//中序遍历
public void infixOrder() {
if(root != null) {
root.infixOrder();
}else {
System.out.println("树为空 无法遍历");
}
}
//查找要删除的节点
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);
}
}
//node 传入的节点（当做二叉排序树的根节点）
//返回该二叉排序树的最小节点的值 并删除该值
public int delRightTree(Node node) {
Node target = node;
//循环查找右子树的左节点 找到最小值
while(target.left != null) {
target = target.left;
}
//这是target指向最小节点 删除
delNode(target.value);
return target.value;
}
//删除节点
public void delNode(int value) {
if(root == null) {
return;
}
// 要删除的节点
Node targetNode = search(value);
if(targetNode == null) {
return ;
}
if(root.left == null &&root.right == null) {
//只有一个节点
root = null;
return;
}
Node parent = searchParent(value);
if(targetNode.left == null && targetNode.right == null ) {
//节点为叶子结点
//判断targetNode是其父节点的左子节点还是右子节点
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 = delRightTree(targetNode.right);
targetNode.value = minVal;
} else {
// 删除只有一颗子树的节点
if (targetNode.left != null) {
if (parent != null) {// 非根节点
// 有左子节点
if (parent.left.value == value) {
// 是左子节点
parent.left = targetNode.left;
} else {
// 是右子节点
parent.right = targetNode.left;
}
} else {
root = targetNode.left;
}
} // 有右子节点
else {
if (targetNode.right != null) {
if (parent.left.value == value) {
// 是左子节点
parent.left = targetNode.right;
} else {
// 是右子节点
parent.right = targetNode.right;
}
} else {
root = targetNode.right;
}
}
}
}
}
//节点
class Node{
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
public String toString() {
return "Node [value=" + value + "]";
}
//添加节点
//递归 需要满足二叉排序树
public void add(Node node) {
if(node == null) {
return;
}else {
//判断传入的节点的值 和当前子树的根节点的关系
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();
}
}
//查找要删除的节点
public Node search(int value) {
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;
}
}
}
}