前言： 不同数列存储方式的优缺点： 数组：下标查找，查找速度快。缺点：添加慢。 链表：添加速度块。缺点：查找慢。 树存储：利用二叉排序树，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。
二叉排序树 (Binary Sort(Search) Tree)，又叫二叉查找树。对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。 相同的值，可将该节点放在左子节点或右子节点。
二叉排序树分析： 给定一示例数组，[7，3，10，12，5，1，9] 构建二叉排序树步骤如下： 首先取数组第一个元素作为树的根节点： 取出数组第二个节点，与根元素比较，小于7作为左子树 接着取下一个元素，与7比较大小，大于7，作为右子树 继续遍历取数组元素，比价大小后放置。 最后的效果图便是： 创建二叉排序树参考代码：
package Tree07; public class BinarySortTreeDemo { public static void main(String[] args) { int[] arr= {7,3,10,12,5,1,9}; BinarySortTree binarySortTree=new BinarySortTree(); //循环的添加节点到二叉排序树 for(int i=0;i<arr.length;i++) { binarySortTree.add(new Node(arr[i])); } //中序遍历二叉树 binarySortTree.middleShow(); } } //创建二叉排序树 class BinarySortTree{ private Node root; //添加节点的方法 public void add(Node node) { if(root==null) { root=node;//如果root为空则直接让node作为root }else { root.add(node); } } //中序遍历 public void middleShow() { if(root!=null) { root.middleShow(); }else { System.out.println("树为空，不能遍历"); } } } //创建Node节点 class Node{ int value; Node left; Node right; public Node(int value) { this.value=value; } //添加节点的方法 //递归的形式添加节点 public void add(Node node) { if(node==null) { return; } //判断传入的节点的值，和当前树的根节点的值关系 if(node.value<this.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 middleShow() { if(this.left!=null) { this.left.middleShow(); } System.out.print(this.value+" "); if(this.right!=null) { this.right.middleShow(); } } }运行结果：
二叉排序树的删除情况可能有三种： 1.删除叶子节点，比如上图中的2，5，9，12。 2.删除只有一颗子树的节点，比如上图中的节点1. 3.删除有两棵子树的节点，如上图中的节点 3，10，7.
那么删除的思路分析便要分三种情况 1.删除叶子节点 1）先找到要删除的节点 2）再找到要删除节点的父节点（可能是根节点，要先判断是否有父节点） 3）确定目标节点是左子节点还是右子节点 4)左子节点，令父节点的左子节点为空，右子节点，令父节点的右子节点为空。 2.删除只有一棵子树的节点 1）先找到要删除的节点 2）再找到要删除节点的父节点（可能是根节点，要先判断是否有父节点） 3)确定目标节点的子节点是左子节点还是右子节点 4)确定目标节点是它的父节点的左子节点还是右子节点 5.1）当删除的目标节点是它的父节点的左子节点，那么删除后它的子节点放到目标节点父节点的左子节点。 5.2）当删除的目标节点是它的父节点的右子节点，那么删除后它的子节点放到目标节点父节点的右子节点。 3.删除有两棵子树的节点 1）先找到要删除的节点 2）再找到要删除节点的父节点 3）从目标节点的右子树中找到最小的节点 4）用一个临时变量，将最小节点的值保存到temp 5）删除该最小节点 6）将目标节点赋给最小节点。
代码分析： 首先在Node类中实现根据传入值查找当前节点和其父节点的两种方法 如下：
//查找要删除的节点 public Node search(int value) { if(value==this.value) { return this; }else if(value<this.value) {//查找的之小于当前节点的值，向左子树递归查找 //左子树为空的情况 if(this.left==null) { return null; } return this.left.search(value); }else {//不小于当前节点，向右子树递归查找 if(this.right==null) { return null; } return this.right.search(value); } } //查找要删除节点的父节点 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); }else if(value>=this.value&&this.right!=null) { return this.right.searchParent(value); }else{ return null;//没有找到父节点 } } }之后便可以实现deleteNode方法（根据上面的代码分析）
//删除节点 public void delNode(int value) { if(root==null) { return; }else { //首先找到要删除节点 targetNode Node targetNode=search(value); //可能找不到节点 if(targetNode==null) { return; } //如果我们发现当前这颗二叉树只有一个节点 if(root.left==null&&root.right==null) { root=null; return; } //去找targetNode的父节点 Node parent=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) { //如果tatgetNode是parent的左子节点 if(parent.left.value==value) { parent.left=targetNode.left; }else {//targetNode是parent的右子节点 parent.right=targetNode.left; } }else {//删除的节点有右子节点 //如果tatgetNode是parent的左子节点 if(parent.left.value==value) { parent.left=targetNode.right; }else {//targetNode是parent的右子节点 parent.right=targetNode.right; } } } } } //返回以node为根节点的二叉排序树的最小节点的值 //删除node为根节点的二叉排序树的最小节点 public int delRightTreeMin(Node node) { Node target=node; //循环查找左节点，就会找到最小值 while(target.left!=null) { target=target.left; } //这时target指向了最小节点 //删除最小节点 delNode(target.value); return target.value; }全部代码：
package Tree07; public class BinarySortTreeDemo { public static void main(String[] args) { int[] arr= {7,3,10,12,5,1,9,2}; BinarySortTree binarySortTree=new BinarySortTree(); //循环的添加节点到二叉排序树 for(int i=0;i<arr.length;i++) { binarySortTree.add(new Node(arr[i])); } //中序遍历二叉树 System.out.println("中序遍历结果如下："); binarySortTree.middleShow(); //binarySortTree.delNode(2); //binarySortTree.middleShow(); System.out.println(); binarySortTree.delNode(7); binarySortTree.middleShow(); } } //创建二叉排序树 class BinarySortTree{ private Node root; //删除节点 public void delNode(int value) { if(root==null) { return; }else { //首先找到要删除节点 targetNode Node targetNode=search(value); //可能找不到节点 if(targetNode==null) { return; } //如果我们发现当前这颗二叉树只有一个节点 if(root.left==null&&root.right==null) { root=null; return; } //去找targetNode的父节点 Node parent=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) { //如果tatgetNode是parent的左子节点 if(parent.left.value==value) { parent.left=targetNode.left; }else {//targetNode是parent的右子节点 parent.right=targetNode.left; } }else {//删除的节点有右子节点 //如果tatgetNode是parent的左子节点 if(parent.left.value==value) { parent.left=targetNode.right; }else {//targetNode是parent的右子节点 parent.right=targetNode.right; } } } } } //返回以node为根节点的二叉排序树的最小节点的值 //删除node为根节点的二叉排序树的最小节点 public int delRightTreeMin(Node node) { Node target=node; //循环查找左节点，就会找到最小值 while(target.left!=null) { target=target.left; } //这时target指向了最小节点 //删除最小节点 delNode(target.value); return target.value; } //查找以node根节点的二叉排序树的最小节点的 //查找要删除节点 public Node search(int value) { if(root==null) { return null; }else { return root.search(value); } } //查找删除节点的父节点 public Node searchParent(int value) { if(root==null) { return null; }else { return root.searchParent(value); } } //添加节点的方法 public void add(Node node) { if(root==null) { root=node;//如果root为空则直接让node作为root }else { root.add(node); } } //中序遍历 public void middleShow() { if(root!=null) { root.middleShow(); }else { System.out.println("树为空，不能遍历"); } } } //创建Node节点 class Node{ int value; Node left; Node right; public Node(int value) { this.value=value; } //查找要删除的节点 public Node search(int value) { if(value==this.value) { return this; }else if(value<this.value) {//查找的之小于当前节点的值，向左子树递归查找 //左子树为空的情况 if(this.left==null) { return null; } return this.left.search(value); }else {//不小于当前节点，向右子树递归查找 if(this.right==null) { return null; } return this.right.search(value); } } //查找要删除节点的父节点 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); }else if(value>=this.value&&this.right!=null) { return this.right.searchParent(value); }else{ return null;//没有找到父节点 } } } //添加节点的方法 //递归的形式添加节点 public void add(Node node) { if(node==null) { return; } //判断传入的节点的值，和当前树的根节点的值关系 if(node.value<this.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 middleShow() { if(this.left!=null) { this.left.middleShow(); } System.out.print(this.value+" "); if(this.right!=null) { this.right.middleShow(); } } }