排序二叉树删除节点

假设在二叉排序树上被删结点为p(指向结点的指针为p)，其双亲结点为f(结点指针为f)，且不失一般性，可设p是f的左孩子。

下面分三种情况进行讨论：

(1)若p结点为叶子结点，即PL和PR均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。

(2)若p结点只有左子树PL或者只有右子树PR，此时只要令PL或PR直接成为其双亲结点f的左子树即可。显然，作此修改也不破坏二叉排序树的特性。

(3)若p结点的左子树和右子树均不空。图(b)可知，在删去p结点之前，中序遍历该二叉树得到的序列为{…CLC…QLQSLSPPRF…}，在删去p之后，为保持其它元素之间的相对位置不变，可以有两种做法：其一是令p的左子树为f的左子树，而p的右子树为s的右子树，如图(c)所示；其二是令p的直接前驱(或直接后继)替代p，然后再从二叉排序树中删去它的直接前驱(或直接后继)。如图(d)所示，当以直接前驱s替代p时，由于s只有左子树SL，则在删去s之后，只要令SL为s的双亲q的右子树即可。

二叉排序树不过是提供一种数据结构，如果没有应用，它的存在没有任何意义。所以随便怎么样都行，看你的具体需求。
如果你实际应用中允许相同的值，那么向左向右插入都可以，你只要保证你的树在中序遍历时是非严格单调递增即可
如果你实际应用中要求值唯一，那么你的实现应该以某种形式告诉用户，比如说返回某个特殊值，或者抛出异常

---