一、概念
二叉搜索树又称二叉排序树，是一种可以进行快速查询的二叉树类型。
所具有的性质：
- 若节点不为空，根节点的值大于其左子树任一节点的值。
- 若节点不为空，根节点的值小于其右子树任一节点的值。
- 任一节点的左右子树均为二叉搜索树
其性质的特点在于中序遍历的结果一定是升序的（如下图）
编辑
二、基本操作实现
准备工作：
创建二叉树结点，以及根节点：
//创建二叉树结点 public static class Node{ int val; Node left; Node right; public Node(int val) { this.val = val; } } //根节点 private static Node root =null;
1、查找元素
思路：结合二叉搜索树的特性，节点的左树节点值都比其小，右树节点都比其大的特性，我们从根节点的值与寻找元素比较，如果根节点小就向右树进行寻找，反之向左树寻找。
//查询元素 public Node search(int key) { if (root == null) { return null; } //定义一个遍历节点 Node cur = root; while (cur != null) { //寻找到返回节点 if (key == cur.val) { return cur; //节点值小时向右树寻找 }else if (key > cur.val) { cur = cur.right; //节点值大时向左树寻找 } else { cur = cur.left; } } return null; }
2、插入元素
思路：同样结合二叉搜索树的特性，节点的左树节点值都比其小，右树节点都比其大的特性。用cur节点去遍历二叉树，如果插入元素大于节点值就向树的右边遍历，反之向左边遍历。找到合适的位置即可（插入的元素一定都是放在叶子节点上）
为什么插入的元素一定在叶子节点上呢？
编辑
这里的8是我们插入的元素，为什么会放在叶子节点上？是因为我们这个元素要不是比节点小要不就是大（二叉搜索树不可以包含相同的元素）并且不会存在大小相同的元素，那么他就会一直遍历下去寻找要插入的位置直到叶子节点结束（相对于叶子节点要不大就放在叶子右边要不小就放在叶子左边）
public boolean insert(int key) { if (root == null) { root = new Node(key); return true; } //cur为遍历节点 Node cur = root; //因为cur一直遍历最后会变成null无法找到上一个节点 //所以创建一个parent标记cur上一个节点 Node parent = null; while (cur != null) { //插入元素比节点值大向右遍历 if (cur.val > key) { parent = cur; cur = cur.left; //插入元素比节点值小向左遍历 } else if (cur.val < key) { parent = cur; cur = cur.right; } else return false; } Node node = new Node(key); if (parent.val < key) { parent.right = node; } else { parent.left = node; } return true; }
三、删除元素
所要考虑的问题：
一、所要删除的元素需要先找到这个节点所在的位置
二、分情况讨论所要删除元素左右树的情况（是否为null）
三、如果左右树都不为null，删除节点位置应该置为什么？
1.1、寻找所要删除的节点
思路：我们需要遍历二叉搜索树，寻找所要找的节点记录下来，并且记录下它的上一个节点（因为在删除当前节点后，需要让上一个节点与删除节点的下一个节点做链接）。如果找到这个节点就调用removeNode方法去做我们的删除节点操作。
public void remove(int key) { //遍历节点 Node cur = root; //遍历节点的上一个节点 Node parent = null; while (cur != null) { if (cur.val < key) { parent = cur; cur = cur.right; } else if (cur.val >key) { parent = cur; cur = cur.left; } else { removeNode(cur,parent); System.out.println(key+"所在结点删除成功"); return; } } }
2.1、讨论删除节点左右树的情况
所有情况：
1、删除节点的左节点为空（可能为根节点）
if (cur.left == null) { if (cur == root) { root = root.right; } else if(cur == parent.left) { parent.left = cur.right; } else { parent.right = cur.right; }
2、删除节点的右节点为空（可能为根节点）
if (cur.right == null) { if (cur == root) { root = root.left; } else if (cur == parent.left) { parent.left = cur.left; } else { parent.right = cur.left; }
3、删除节点左右树不为空（可能为根节点）
替代的节点只能是：
删除节点左树中最大的节点（最右下边的节点）
删除节点右数中最小的节点（最左下的节点）
先上代码下面详解
Node tParent = cur; Node t = cur.right; while (t.left != null) { tParent = t; t = t.left; } cur.val = t.val; if (tParent.right == t) { tParent.right = t.right; } else { tParent.left = t.right; }
4、删除节点为null（不存在）
if (cur==null) { return; }
删除节点左右树不为空的情况是我们最难理解的。先看下面的图
编辑
先看7和11的位置。7是 删除节点9作数中最大值的节点，11是删除节点9的右树中最小值的节点。
替代的节点只能是：
删除节点左树中最大的节点（最右下边的节点）
删除节点右数中最小的节点（最左下的节点）
因为节点的左数比其都小，右树都比其大的特性（仔细理解这个话）。只有这两个与删除节点最近值的节点才能代替删除的节点。
完整代码：
public class BinarySearchTree { public static void main(String[] args) { BinarySearchTree binarySearchTree = new BinarySearchTree(); binarySearchTree.insert(8); binarySearchTree.insert(12); binarySearchTree.insert(3); binarySearchTree.insert(6); binarySearchTree.insert(9); binarySearchTree.insert(1); binarySearchTree.insert(13); System.out.println(); binarySearchTree.order(root); binarySearchTree.remove(8); binarySearchTree.order(root); } public static class Node{ int val; Node left; Node right; public Node(int val) { this.val = val; } } //根节点 private static Node root =null; //插入元素 /** * * @param key 搜索树的性质不能有重复的值 * @return 是否成功 */ public boolean insert(int key) { if (root == null) { root = new Node(key); return true; } //cur为遍历节点 Node cur = root; //因为cur一直遍历最后会变成null无法找到上一个节点 //所以创建一个parent标记cur上一个节点 Node parent = null; while (cur != null) { //插入元素比节点值大向右遍历 if (cur.val > key) { parent = cur; cur = cur.left; //插入元素比节点值小向左遍历 } else if (cur.val < key) { parent = cur; cur = cur.right; } else return false; } Node node = new Node(key); if (parent.val < key) { parent.right = node; } else { parent.left = node; } return true; } //查询元素 public Node search(int key) { if (root == null) { return null; } //定义一个遍历节点 Node cur = root; while (cur != null) { //寻找到返回节点 if (key == cur.val) { return cur; //节点值小时向右树寻找 }else if (key > cur.val) { cur = cur.right; //节点值大时向左树寻找 } else { cur = cur.left; } } return null; } public void order(Node node) { if (node == null) { return; } order(node.left); System.out.print(node.val+" "); order(node.right); } //删除元素 public void remove(int key) { //遍历节点 Node cur = root; //遍历节点的上一个节点 Node parent = null; while (cur != null) { if (cur.val < key) { parent = cur; cur = cur.right; } else if (cur.val >key) { parent = cur; cur = cur.left; } else { removeNode(cur,parent); System.out.println(key+"所在结点删除成功"); return; } } } public void removeNode(Node cur,Node parent) { //删除元素左边为null if (cur==null) { return; } if (cur.left == null) { if (cur == root) { root = root.right; } else if(cur == parent.left) { parent.left = cur.right; } else { parent.right = cur.right; } } else if (cur.right == null) { if (cur == root) { root = root.left; } else if (cur == parent.left) { parent.left = cur.left; } else { parent.right = cur.left; } } else { Node tParent = cur; Node t = cur.right; while (t.left != null) { tParent = t; t = t.left; } cur.val = t.val; if (tParent.right == t) { tParent.right = t.right; } else { tParent.left = t.right; } } } }
