二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树
二叉树查找树是一棵空树，或者是具有下列性质的二叉树：
若左子树不空，则左子树上所有结点的值均小于它的根结点的值；若右子树不空，则右子树上所有结点的值均大于它的根结点的值；左、右子树也分别为二叉排序树；没有键值相等的结点现实中可以有键值相等的结点，需要自定义规则相等的结点应该放左子树还是右子树，尽量避免键值相等
一棵二叉查找树：
如何创建二叉查找树？设置对应的添加结点的方法
在每次添加结点时，判断当前结点与添加结点的键值大小，小于则放在左子结点，大于放在右子结点
结点键值数组:7,3,10,12,5,1,9,11,13,2
Java实现：
树结点：
实现添加结点方法实现中序遍历：先遍历左子树，再打印父结点，再遍历右子树 //树结点 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 infixOrder(){ if (this.left != null){ this.left.infixOrder(); } System.out.print(this); if (this.right != null){ this.right.infixOrder(); } } @Override public String toString() { return "[value=" + value+"]"; } }二叉树排序树：
//二叉排序树 class BinarySortTree{ //根结点 private Node root; //添加结点的方法 public void add(Node node){ if (root == null){ //空树,直接加入 root = node; } else { //add方法递归加入 root.add(node); } } //中序遍历 public void infixOrder(){ if (root != null){ root.infixOrder(); } else { System.out.println("=== 二叉排序树为空 ==="); } } }测试类：
public class BinarySortTreeDemo { public static void main(String[] args) { int[] arr = {7,3,10,12,5,1,9,11,13,2}; BinarySortTree binarySortTree = new BinarySortTree(); //将数组加入二叉树排序树 for (int i : arr){ binarySortTree.add(new Node(i)); } //中序遍历二叉树排序树 1,2,3,5,7,9,10,11,12,13 binarySortTree.infixOrder(); } }中序遍历结果：1,2,3,5,7,9,10,11,12,13
对于一棵二叉查找树，删除结点需要考虑：
删除的是叶子结点，直接将要删除的结点targetNode的父结点parent的对应子结点置空即可 删除结点有一棵子树（左或右），删除目标结点targetNode时，还需要将子结点顶替当前位置 删除结点有两棵子树，这个时候需要选择：将左子树最大值顶替目标结点、将右子树最小值顶替目标结点 这里选择将右子树最小值顶替目标结点删除功能需要考虑许多情况：
二叉树为空，直接返回没有找到，直接返回二叉树只有一个根结点，找到根结点，将根置空目标结点是根节点，parent为空，就不能parent.left，parent.right这再后续的代码将一一考虑
上面的方法都用到了targetNode和parent，需要写方法查找待删除结点和它的父结点
Java实现删除：
在结点类添加方法：
查找结点Node search(int value)：比较当前结点值与查找结点值，相对即查到，大于往右子树递归，小于往左子树递归查找目标结点的父结点Node searchParent(int value) //树结点 class Node{ int value; //左右子结点 Node left; Node right; public Node(int value) { this.value = value; } /** * 查找结点 * @param value 查找结点的值 * @return 要查找的结点，没找到返回null */ public Node search(int value){ if (value == this.value){ //找到就是该结点 return this; } else if (value < this.value){ //查找的值小于当前结点，向左子树递归查找 //如果存在左子结点 if (this.left != null) { return this.left.search(value); } else { //不存在左子结点，说明查找不到 return null; } } else { //查找的值大于当前的值,向右子树递归查找 //如果存在右子结点 if (this.right != null){ return this.right.search(value); } else{ //不存在右子结点，说明查找不到 return null; } } } /** * 查找结点的父结点 * @param value 要查找结点的值 * @return 返回要查找的结点的父结点，没有就返回null */ 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 infixOrder(){ if (this.left != null){ this.left.infixOrder(); } System.out.print(this); if (this.right != null){ this.right.infixOrder(); } } @Override public String toString() { return "[value=" + value+"]"; } }二叉排序树，添加7个方法：
从根结点开始查找待删除的结点Node search(int value)从根结点开始查找待删除的结点的父结点Node searchParent(int value)查找并删除右子树的最小结点Node delRightTreeMin(Node node)，用于第三种删除方法删除叶子结点delLeafNode(Node parent,int value)，有父结点就够了删除有一棵子树（左或右）的结点delNodeOneTree(Node parent,Node targetNode,int value)删除有左右子树的结点delNodeTwoTree(Node parent,Node targetNode)封装删除方法delNode(int value)，传入带删除结点的键值 //二叉排序树 class BinarySortTree{ //根结点 private Node root; //添加结点的方法 public void add(Node node){ if (root == null){ //空树,直接加入 root = node; } else { //add方法递归加入 root.add(node); } } //中序遍历 public void infixOrder(){ if (root != null){ root.infixOrder(); } else { System.out.println("=== 二叉排序树为空 ==="); } } //从根节点查找要删除的结点 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); } } /** * 删除右子树的最小结点并返回 * @param node 传入的结点，当做一个二叉排序树的根节点 * @return 返回以node为根结点的二叉排序树的最小结点 */ public Node delRightTreeMin(Node node){ Node temp = node; //循环查找左子结点，找到最小值 while (temp.left != null){ temp = temp.left; } //temp指向最小结点,删除并返回 delNode(temp.value); return temp; } /** * 删除结点：如果要删除的结点有一棵子树 * @param parent 要删除结点的父结点 * @param targetNode 要删除的结点 * @param value 要删除的结点的值 */ public void delNodeOneTree(Node parent,Node targetNode,int value){ //如果要删除的结点只有左子树 if (targetNode.left != null){ if (parent != null) { //如果targetNode是parent的左子结点 if (parent.left.value == value) { parent.left = targetNode.left; } else { //targetNode是parent的右子结点 parent.right = targetNode.left; } }else { //如果要删除的结点是根节点 root = targetNode.left; } } //要删除的结点只有右子树 else { if (parent != null) { if (parent.left.value == value) { parent.left = targetNode.right; } else { //targetNode是parent右子结点 parent.right = targetNode.right; } } else { //删除的是根节点 root = targetNode.right; } } } /** * 删除结点：如果要删除的结点有左右子树 * @param parent 要删除结点的父结点 * @param targetNode 要删除的结点 */ public void delNodeTwoTree(Node parent,Node targetNode){ //得到右子树的最小值 Node min = delRightTreeMin(targetNode.right); //将最小结点替换删除的结点,达成删除结点的效果 min.left = targetNode.left; min.right = targetNode.right; if (parent != null) { if (parent.left == targetNode) { parent.left = min; } else { parent.right = min; } } } /** * 删除结点：如果要删除的结点有一棵子树 * @param parent 要删除结点的父结点 * @param value 要删除的结点的值 */ public void delLeafNode(Node parent,int value){ //判断targetNode 是 父结点的左、右子结点 if (parent.left != null && parent.left. value == value){ //删除的结点是父结点的左子结点 parent.left = null; } else if (parent.right != null && parent.right.value == value){ //删除的结点是父结点的右子结点 parent.right = null; } } //删除结点 public void delNode(int value){ if (root == null){ return; } //查找要删除的结点 Node targetNode = search(value); //判断是否找到 if (targetNode == null){ return; } //如果发现当前这棵二叉树只有一个结点,删除的就是根结点 if (root.left == null && root.right == null){ root = null; return; } //找父结点 Node parent = searchParent(value); //如果要删除的结点是叶子结点 if (targetNode.left == null && targetNode.right == null){ delLeafNode(parent,value); } //如果删除的结点有左右子树 else if (targetNode.left != null && targetNode.right != null){ delNodeTwoTree(parent,targetNode); } //删除只有一棵子树的结点 else { delNodeOneTree(parent,targetNode,value); } } }测试方法：
public class BinarySortTreeDemo { public static void main(String[] args) { int[] arr = {7,3,10,12,5,1,9,11,13,2}; BinarySortTree binarySortTree = new BinarySortTree(); //将数组加入二叉树排序树 for (int i : arr){ binarySortTree.add(new Node(i)); } //中序遍历二叉树排序树 1,2,3,5,7,9,10,11,12,13 binarySortTree.infixOrder(); System.out.println(); //测试删除叶子结点 binarySortTree.delNode(9); System.out.println("=== 删除结点9后 ==="); binarySortTree.infixOrder(); System.out.println(); //测试删除有一棵子树的结点 System.out.println("=== 删除结点1后 ==="); binarySortTree.delNode(1); binarySortTree.infixOrder(); System.out.println(); //测试删除有左右结点的结点 System.out.println("=== 删除结点10后 ==="); binarySortTree.delNode(10); binarySortTree.infixOrder(); } }删除9，1，10后：中序遍历为2,3,5,7,11,12,13
二叉排序树完整代码：gitee
