二叉搜索树概念
又称作二叉查找树。
定义引用自《算法导论第三版》
二叉搜索树中的关键字总是以满足二叉搜索树性质的方式来存储：
设x是二叉搜索树中的一个结点。如果y是x左子树中的一个结点，那么y.key<=x.key。如果y是x 右子树中的一个结点，那么y.key>=x.key。
如果下图所示，结点关键字值均大于其左子树的关键值，小于其右子树的关键值。这里为了便于下文算法的展示做了处理，假设所有节点的关键值不相等，并且关键字为18的节点代表后插入的节点用虚线画出。
二叉搜索树
二叉搜索树算法Java实现
二叉搜索树节点的定义
public class TreeNode {
private int code;
private TreeNode left;
private TreeNode right;
TreeNode(int code) {
this.code = code;
}
public int getCode() {
return code;
}
public void setCode(int code) {
this.code = code;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
}
二叉搜索树查找
因为二叉搜索树的性质，沿着树中一棵简单路径向下进行查询，如果两个关键字相等，查找成功；否则直到树的节点为null，查找终止。时间复杂 度O(h)，h为树高。
public boolean find(TreeNode root, int val){
if (null == root){
return false;
}
//从树根开始沿着简单路径向下查找
while (root != null){
if (root.getCode() == val){
return true;
} else if (root.getCode() > val){
root = root.getLeft();
} else {
root = root.getRight();
}
}
return false;
}
二叉搜索树插入
新节点插入到二叉搜索树的叶子节点处，从根节点出发沿着树的一条简单路径找到新节点插入的位置。时间复杂 度O(h)，h为树高。例如上图插入新的关键字值为18的节点。
public void insert(TreeNode root, TreeNode insNode){
if (null == root){
root = insNode;
return;
}
while (root != null){
//如果节点关键字值存在，则不插入
if (root.getCode() == insNode.getCode()){
return;
} else if (root.getCode() > insNode.getCode()){
//如果插入关键字值小于当前节点关键字值，向左子树查找
//如果此时当前节点的左子树为null，直接将新节点插入
if (null == root.getLeft()){
root.setLeft(insNode);
return;
}
//左子树不为null，继续遍历
root = root.getLeft();
} else {
//右子树遍历与左子树相同
if (null == root.getRight()){
root.setRight(insNode);
return;
}
root = root.getRight();
}
}
}
二叉搜索树删除
删除操作比起插入和查找都要复杂的多，是二叉搜索树的重点。尤其在面试的时候如果面试官想考察二叉搜索树的代码，一定会让面试者写删除节点的代码。我们从两方面介绍二叉搜索树的删除操作，首先是删除的整体思路，这个在各个教材中都有介绍，比起之后的红黑树和AVL树而已要简单的多，因为不涉及维持树平衡性质的左旋和右旋操作。其次就是代码的实现，具体代码实现比起讲述的过程要复杂，因为其中有许多细节要格外注意。
- 删除算法
- 如果删除的节点只有一个子节点，直接删除节点，子节点替换；
- 如果删除的节点有两个孩子，找到其后继节点
- 如果后继节点是删除节点的右孩子，右孩子替换当前节点，删除节点的左子树为新节点（原来的右孩子）的左子树
- 如果后继节点是右孩子左子树中的节点，后继节点替换当前节点，后继节点的右子树替换后继节点
二叉搜索树删除--摘自《算法导论第三版》
简而言之，删除节点如果有一个子节点，子节点直接替换删除节点；如果有两个节点，找后继节点，后继节点是删除节点的右孩子，直接替换删除节点，后继节点不是删除节点的右孩子，替换删除节点后，后继节点的子节点替换后继节点。
- Java代码实现
按照上面的逻辑编写代码，虽然不是最简洁的，但是是我认为最好理解的，这里需要注意三点细节：
- 遍历节点时需要记录删除节点的父节点
- 记录删除节点是其父节点的左孩子还是右孩子
- 具有一个子节点的情况下，根节点的父节点为null，需要单独处理
public TreeNode remove(TreeNode root, int val){
if (null == root){
return root;
}
//记录当前查找的节点
TreeNode node = root;
//记录当前节点的父节点
TreeNode parent = null;
//记录当前节点是其父节点的左孩子还是右孩子
boolean rightChild = true;
while (node != null){
//按照二叉搜索树性质查找将要删除的节点
if (node.getCode() > val){
parent = node;
node = node.getLeft();
rightChild = false;
} else if (node.getCode() < val){
parent = node;
node = node.getRight();
rightChild = true;
} else if (node.getRight() != null && node.getLeft() != null){//删除的节点有两个子节点
if (node.getRight().getLeft() == null){//后继节点是删除节点的右孩子
//右孩子替换删除节点
node.setCode(node.getRight().getCode());
node.setRight(node.getRight().getRight());
break;
}
//后继节点不是删除节点的右孩子
parent = findMinParent(node.getRight(), node);//查找删除节点的后继节点的父节点
//后继节点替换删除节点
node.setCode(parent.getLeft().getCode());
//后继节点的右孩子替换后继节点
parent.setLeft(parent.getLeft().getRight());
break;
} else {//删除的节点具有一个子节点（如果是叶子节点相当于有一个为null的子节点）
if (null == parent){//根节点单独处理，直接下移剔除根节点即可
root = root.getLeft() != null ? root.getLeft() : root.getRight();
return root;
}
if (node.getLeft() != null){//如果删除节点的左子树不为null
if (rightChild){//删除节点是右孩子，其左子树替换
parent.setRight(node.getLeft());
} else {
parent.setLeft(node.getLeft());
}
} else {//如果删除节点的右子树不为null，与左子树相反
if (rightChild){
parent.setRight(node.getRight());
} else {
parent.setLeft(node.getRight());
}
}
break;
}
}//while
return root;
}
/**
* 查找删除节点的后继节点的父节点
*/
private TreeNode findMinParent(TreeNode root, TreeNode parent){
while (root.getLeft() != null){
parent = root;
root = root.getLeft();
}
return parent;
}
总结
二叉搜索树是树知识中的基础，也是未来将要学习的平衡搜索树的基础。夯实的基础是进阶的必备条件。
