package com.atguigu.binarysorttree;/**** 二叉排序树***/
public class BinarySortTreeDemo{public static void main(String[] args) {int[] arr={7, 3, 10, 12, 5, 1, 9, 0};BinarySortTree binarySortTree = new BinarySortTree();//循环的添加结点到二叉排序树for(int i = 0; i< arr.length; i++) {binarySortTree.add(new Node(arr[i]));}//中序遍历二叉排序树System.out.println("中序遍历二叉排序树~");binarySortTree.infixOrder(); // 1, 3, 5, 7, 9, 10, 12//测试一下删除叶子结点//        binarySortTree.delNode(12);
//
//
//        binarySortTree.delNode(5);
//        binarySortTree.delNode(10);
//        binarySortTree.delNode(2);
//        binarySortTree.delNode(3);
//
//        binarySortTree.delNode(9);
//        binarySortTree.delNode(1);binarySortTree.delNode(7);System.out.println("root=" + binarySortTree.getRoot());System.out.println("删除结点后");binarySortTree.infixOrder();}}//添加结点的方法
class BinarySortTree{private Node root;public Node getRoot(){return root;}//中序遍历public void add(Node node){if(root == null) {root = node;//如果root为空则直接让root指向node} else {root.add(node);}}public void infixOrder(){if(root==null){System.out.println("二叉树为空");}else{root.infixOrder();}
}public int delRightTreeMin(Node node){Node target=node;while(target.left!=null){target=target.left;}delNode(target.value);return target.value;
}public void delNode(int value) {if (root == null) {return;} else {Node targetNode = root.search(value);if (targetNode == null) {return;}if (root.left == null && root.right == null) {root = null;return;}//去找到targetNode的父结点Node parent = root.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=delRightTreeMin(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 (parent != 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;}@Overridepublic String toString() {return "Node{" +"value=" + value +'}';}//查找要删除的结点/**** @param value 希望删除的结点的值* @return 如果找到返回该结点，否则返回null*/public  Node search(int value){if(value==this.value){      //找到该节点return this;}else if(value<this.value){if(this.left!=null) {return this.left.search(value);}return null;}else{if(this.right!=null) {return this.right.search(value);}return null;}}//查找要删除结点的父结点/**** @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);}if(value>=this.value&&this.right!=null){return  this.right.searchParent(value);}else{return null;}}
}//添加结点的方法//递归的形式添加结点，注意需要满足二叉排序树的要求public  void add(Node node){if(this.value>node.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();}
}}