二叉排序树(二叉查找树)BST构造，节点插入，节点查找，节点删除(java)

• 二叉排序树(BST)的构造，节点插入，节点查找，节点删除(java)
  高度最小BST(同样数据，顺序可能不一样)

package ccnu.offer.tree;import java.util.ArrayList;
import java.util.Arrays;// 二叉排序树(二叉查找树)BST
// 对于给定数组(数据完全一样，并且数据顺序一定)构造二叉排序树一定，但是数据一样，顺序不一样，那么排序树就不一样
// 构造高度最小的二叉排序树，那么就需要有如下要求：尽可能将数组中还未插入的数据的中位数作为根节点
public class Demo04 {
    public static void main(String[] args) {int[] datas = new int[]{
   53, 17, 78, 9, 45, 65, 94, 23, 81, 88}; // page149:4-22Node root = null;root = removeBSTNode(createBST(root, datas), 78);inOrder(root);}// 二叉排序树的构造:就是不断的插入新节点public static Node createBST(Node root, int[] datas){root = null;int index = 0;while(index < datas.length){root = insertBST(root, datas[index]);index++; // 插入下一个节点}return root;}// 二叉排序树的插入public static Node insertBST(Node root, int data){ // 插入的新节点一定为叶子if(root == null){ // 以root为根节点的树为空树root = new Node(data); // 左右子树均为空}/*else if(data == root.data){ // 已存在此值的节点return root;}*/else if(data <= root.data){ // 插入到root的左子树上root.lchild = insertBST(root.lchild, data);}else{ // 插入到root的右子树上root.rchild = insertBST(root.rchild, data);}return root;}// 二叉查找树中查找指定关键字值节点public static Node searchBST(Node root, int data){Node p = null; // 此处可得到所要找到节点的父节点while(root != null && root.data != data){ // 当前树非空并且所找节点不是当前树的根节点p = root;if(data < root.data){root = root.lchild;}else{root = root.rchild;}}/*if(root == null){p = null;}*/
// return root;return p; // 返回找到节点的父节点,当p为null,则说明找到的节点为整棵树的根节点}// 得到指定树root中父节点p的关键字值为data的孩子节点public static Node getChild(Node root, Node p, int data){if(p == null){ // 父节点为空，则找到的关键字值为data的节点为整棵树的根节点rootreturn root;}if(p.lchild == null && p.rchild == null){ // 如果父节点为叶子节点，那么不存在指定data节点return null;}if(p.lchild != null && p.lchild.data == data){return p.lchild;}else{return p.rchild;}}public static Node searchBST1(Node root, int data){if(root == null){return null;}else if(root.data == data){return root;}else if(data < root.data){root = searchBST1(root.lchild, data);}else{root = searchBST1(root.rchild, data);}return root;}// 删除以root作为根节点的树中的关键字值为data的节点(第一次出现)public static Node removeBSTNode(Node root, int data) {if (root == null) {return null;}Node p = searchBST(root, data); // 找到节点的父节点Node node = null; // 找到的节点node = getChild(root, p, data);if (node == null) { // 不存在指定删除的节点return root; // 返回原树根节点}if (node.lchild == null && node.rchild == null) { // 要删除的节点为叶子结点,就直接从其父节点上删除if (node == root) { // 找到的节点为根节点 等价于p为nullroot = null;return root;}// 父节点不为空if (p.lchild != null && p.lchild.data == node.data) { // 如果有左子树并且左子树根节点为找到的节点p.lchild = null; // 直接将这个叶子节点从树中删除} else {p.rchild = null;}node = null; // 删除节点} else if (node.lchild != null && node.rchild == null) { // 只有左子树if (node == root) { // 找到节点为根节点root = null;return node.lchild;}if (p.lchild != null && p.lchild.data == node.data) { // 找到节点为父节点的左孩子节点p.lchild = node.lchild;} else {p.rchild = node.lchild;}} else if (node.lchild == null && node.rchild != null) { // 只有右子树if (node == root) { // 找到节点为根节点root = null;return node.rchild;}if (p.lchild != null && p.lchild.data == node.data) {p.lchild = node.rchild;} else {p.rchild = node.rchild;}} else { // 待删除节点左右子树均有，则应该将待删除节点的直接前驱(中序遍历，比删除节点关键字值不大于节点的最大节点)结点替代，或者// 将待删除节点的直接后继(中序遍历，比删除节点关键字值不小于节点的最小节点)结点替代，进而将问题转换为删除刚才的替代节点// 此处实现的是用删除节点的直接后继结点替代Node nextNode = node.rchild; // 删除节点的直接后继,实际上这个直接后继节点或者是叶子结点或者是只有右子树的节点while (nextNode.lchild != null) {nextNode = nextNode.lchild;}removeBSTNode(node, nextNode.data); // 在待删除的节点为根节点的树中删除其直接后继节点nextNodenextNode.lchild = node.lchild; // 将删除节点的左子树作为后继节点的左子树nextNode.rchild = node.rchild; // 将删除节点的右子树作为后继节点的右子树if (node == root) { // 删除节点为根节点return nextNode;}else{if (p.lchild != null && p.lchild.data == node.data) { // 删除节点在其父节点的左子树上p.lchild = nextNode;} else {p.rchild = nextNode;}}}return root;}public static void inOrder(Node root){ // 中序遍历BST为单调递增序列if(root != null){inOrder(root.lchild);System.out.print(root.data + " ");inOrder(root.rchild);}}private static class Node extends Object{
    private Node lchild = null;private Node rchild = null;private int data;public Node(int data){this.data = data;}}// 得到一组数据的中位数，以这样的数据构造BST将会是平衡二叉树，同时也是所有这些同样数据(顺序不一样)构造的排序二叉树中高度最小的哦public static ArrayList<Integer> getMedians(int[] datas, int begin, int end) {Arrays.sort(datas);ArrayList<Integer> arr = new ArrayList<Integer>();if (begin > end) {return arr; // 空arr} else if (begin == end) {arr.add(datas[begin]);} else {int medium = (begin + end) / 2;arr.add(datas[medium]);arr.addAll(getMedians(datas, begin, medium - 1));arr.addAll(getMedians(datas, medium + 1, end));}return arr;}public static int getDepth(Node root){int ldepth = 0; // 左子树高度int rdepth = 0; // 右子树高度if(root == null){ // 空树深度为0return 0;}ldepth = getDepth(root.lchild);rdepth = getDepth(root.rchild);return (ldepth > rdepth ? ldepth : rdepth) + 1;}
}