二叉排序树定义：
1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 它的左、右子树也分别为二叉排序树。
二叉排序树的常用方法：
添加结点：类似二叉树
遍历：所有遍历和普通二叉树一样
删除结点：重点！！！！
1.删除叶子节点
思路：
（1）找到要删除的结点：targetNode
（2）找到targetNode的父结点parent
（3）确定targetNode是parent的左子结点还是右子结点
（4）根据情况进行删除
2.删除只有一颗子树的结点
思路：
（1）找到要删除的结点：targetNode
（2）找到targetNode的父结点parent
（3）确定targetNode的子树是左子树还是右子树
（4）确定targetNode是parent的左子结点还是右子结点
（5）如果targetNode只有左子树
因为targetNode的左子树都小于targetNode的值，其中最大的就是targetNode.left（即所有小的中挑大的）
5.1 如果targetNode是parent的左子结点
parent.left=target.left
5.2 如果targetNode是parent的右子结点
parent.right=targetNode.left
（6）如果targetNode只有右子树
因为targetNode的右子树都大于targetNode的值，其中最小的就是targetNode.right（即所有大的中挑小的）
6.1 如果targetNode是parent的左子结点
parent.left=targetNode.right
6.2 如果targetNode是parent的右子结点
parent.right=targetNode.right
总结：删除只有一颗子树的结点，在该结点的子树中找到可以替代该子树的结点，替换掉即可
3.删除有两棵子树的结点
思路：
（1）找到要删除的结点targetNode
（2）找到targetNode的父结点parent
（3）从targetNode的右子树找到最小的结点
（4）创建临时变量temp保存最小结点的值
（5）删除最小结点
（6）targetNode.value=temp
思路：删除有两颗子树的结点。首先该结点肯定是大于左边所有结点且小于右边所有结点（即中间值）
找到最接近该结点的值的结点替代要删除的结点即可（左边结点中最大的或者右边结点中最小的）
完整代码如下：对于代码应该认真体会找父结点，递归等思想的实现
//构造结点 public class Node { public int value; public Node left; public 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 midOrder() { if (left != null) { this.left.midOrder(); } Console.WriteLine(this.toString()); if (right != null) { this.right.midOrder(); } } public string toString() { return "结点值为:" + this.value; } } //构造二叉排序树 public class BinarySortTree { public Node root; //添加结点 public void add(Node node) { if (root == null) { root = node; } else { root.add(node); } } //中序遍历 public void midOrder() { if (root != null) { root.midOrder(); } else { Console.WriteLine("当前二叉排序树为空"); } } //查找要删除的结点 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 delNode(int value) { if (root == null) { return; } else { //需要删除的目标结点 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) { //判断target是父结点的左子结点还是右子结点 //要删除结点是父结点的左子结点 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 = Min(targetNode.right); targetNode.value = minVal; } //删除只有一颗子树的结点 else { //如果要删除的结点有左子结点 //targetNode有左子结点 if (targetNode.left != null) { if (parent != null) { //target是parent的左子结点 if (parent.left.value == value) { parent.left = targetNode.left; } else//target是parent的右子结点 { parent.right = targetNode.left; } } else { root = targetNode.left; } } else//要删除的结点有右子结点 { if (parent != null) { //target是parent的左子结点 if (parent.left.value == value) { parent.left = targetNode.right; } else//target是parent的右子结点 { parent.right = targetNode.right; } } else { root = targetNode.right; } } } } } //找到以node结点为根节点的二叉排序树最小结点的值，并删除 public int Min(Node node) { Node target = node; //循环查找左节点 while(target.left!=null) { target = target.left; } //target指向了最小结点，并删除 delNode(target.value); return target.value; } }