二叉排序树介绍

二叉排序树（Binary Sort/Search Tree）：对于二叉排序树的任意一个非叶子节点，左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。

==如果值相同，该节点可以放在左子节点或右子节点==

示例：

复杂度：

不论哪一种操作，所花的时间都和树的高度成正比。因此，如果共有n个元素，那么平均每次操作需要**O(logn)**的时间。

二叉排序树的实现

1. 二叉排序树的创建

构建(就是普通的二叉树)

public class BinarySearchTree {

    private TreeNode root;

    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }
}

public class TreeNode {

    int value;          //节点属性值
    TreeNode left;      //左子节点
    TreeNode right;     //右子节点
    
}

插入

思路：1. 比较插入节点的值与当前节点的值来决定插入位置是左子节点还是右子节点

2. 插入的左子节点为空，则将插入节点设置为左子节点；不为空，则进行递归

//TreeNode：
//添加节点操作
public void add(TreeNode treeNode) {
    //先判断加入的节点是否为空
    if (treeNode == null) {
        return;
    }
    //当加入节点的值小于当前节点的值时，考虑左子节点
    if (treeNode.value < this.value) {
        if (this.left == null) {
            this.left = treeNode;
        } else {
            this.left.add(treeNode);
        }
    } else { //当加入节点的值大于当前节点的值时，考虑右子节点
        if (this.right == null) {
            this.right = treeNode;
        } else {
            this.right.add(treeNode);
        }
    }
}

//BinarySearchTree：
public void add(TreeNode treeNode) {
    if (root == null) {
        return;
    }
    root.add(treeNode);
}

2. 二叉排序树的删除

思路分析：

删除叶子节点：
1. 找到要删除的节点 targetNode
2. 找到要删除的节点的父节点 parentNode
3. 确定 targetNode 是 parentNode 的左子节点还是右子节点
4. （如果是左子节点）parentNode.left = null
  
  （如果是右子节点）parentNode.right = null
删除只有一颗子树的节点
1. 找到要删除的节点 targetNode
2. 找到要删除的节点的父节点 parentNode
3. 确定 targetNode 是 parentNode 的左子节点还是右子节点
  - 是左子节点且有左子节点：
  - 是左子节点且有右子节点：
  - 是右子节点且有左子节点：
  - 是右子节点且有右子节点：
删除有两颗子树的节点：
1. 找到要删除的节点 targetNode
2. 找到 targetNode 的父节点 parentNode
3. 找到 targetNode 节点左子节点，向右递归找到最大的节点 tempNode（没有右子节点就是targetNode的左子节点本身）
  
  或者
  
  找到 targetNode节点右子节点，向左递归找到最小的节点 tempNode（没有左子节点就是targetNode的右子节点本身）
4. targetNode.value = tempNode.value
5. 删除tempNode节点

代码实现：

//TreeNode：

//查找值为 value 的节点
public TreeNode search(int value) {
    if (this.value == value) {
        return this;
    } else if (this.value > value) {
        if (this.left.value == value) {
            return this.left;
        } else {
            return this.left.search(value);
        }
    } else {
        if (this.right.value == value) {
            return this.right;
        } else {
            return this.right.search(value);
        }
    }
}

//查找置为value的节点的父节点
public TreeNode searchParent(int value) {
    //如果当前节点就是要删除的节点的父节点，则返回当前节点
    if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
        return this;
    } else {  //否则则进行递归查找父节点
        if (this.value > value && this.left != null) {
            return this.left.searchParent(value);
        } else if (this.value <= value && this.right != null) {
            return this.right.searchParent(value);
        } else {
            return null;
        }
    }
}

//BinarySearchTree：

public TreeNode search(int value) {
    if (this.root == null) {
        return null;
    }
    return this.root.search(value);
}

public TreeNode searchParent(int value) {
    if (this.root == null) {
        return null;
    }
    return this.root.searchParent(value);
}

/**
 * 删除左子树的最大节点 tempNode
 * @param treeNode 要删除的节点targetNode
 * @return 返回targetNode左子树向右递归得到的最大节点的值
 */
public int delLeftTreeMax(TreeNode treeNode) {
    TreeNode tempNode = treeNode;
    //向右循环寻早最大子树
    while (tempNode.right != null) {
        tempNode = tempNode.right;
    }
    delete(tempNode.value);
    return tempNode.value;
}

public void delete(int value) {
    if (this.root == null) {
        return;
    }
    TreeNode targetNode = search(value);
    //如果没有找到要删除的节点就直接返回
    if (targetNode == null) {
        return;
    }
    //如果是根节点就直接删除
    if (this.root.left == null && this.root.right == null) {
        this.root = null;
        return;
    }
    TreeNode parent = searchParent(value);
    //1.删除叶子节点
    if (targetNode.left == null && targetNode.right == null) {
        if (targetNode == parent.left) {
            parent.left = null;
        } else {
            parent.right = null;
        }
    } else if (targetNode.left != null && targetNode.right != null) {
        //2. 删除有两颗子树的节点
        int temp = delLeftTreeMax(targetNode.left);
        targetNode.value = temp;
    } else {
        //3. 删除只有一个子树的节点
        if (targetNode == parent.left) {        //如果是targetNode是左子节点
            if (targetNode.left != null) {
                parent.left = targetNode.left;
            } else {
                parent.left = targetNode.right;
            }
        } else {        //如果是targetNode是右子节点
            if (targetNode.left != null) {
                parent.right = targetNode.left;
            } else {
                parent.right = targetNode.right;
            }
        }
    }
}