二叉搜索树结点的删除

二叉搜索树结点的插入是很容易实现的：只要递归遍历，插入合适的位置就行了。而删除要复杂许多。

无左右子树的结点删除

先考虑没有左右子树的情形。这种情形最为容易，找到这个结点，free并返回NULL给上一层结点连接使用就行了。

BinTree* DeleteLeafNode(BinTree *node, ElementType DataNeeded){
    if(node == DataNeeded){
        if(node->left == NULL && node->right == NULL){
            free(node);
            return NULL;
        }
    }else if(DataNeeded < node->data){
        node->left = DeleteLeafNode(Node->left);
    }else{
        node->right = DeleteLeafNode(Node->right);
    }
}

最小值结点/最大值结点的删除

删除一棵树中的最小值结点时，需要记录它的右子树，free结点并返回右子树给上一层进行连接。删除最大值结点也一样，要记录左子树，删除并返回左子树给上一层。

BinTree* DeleteMax(BinTree node){
    if(node->right == NULL){//检查到为最大值时
        BinTree maxsLeft = node->left;
        free(node);
        return maxsLeft;//返回以作为连接使用
    }else{
        node->right = DeleteMax(BinTree->right);
        return node;
    }
}

（此为删除最大值结点）

左右子树均存在的结点删除

以上讨论了对于子树单侧存在的结点的删除。对于子树双侧存在的结点，首先要选取其左子树中的最大值取代它，然后删除左子树中的最大值即可。同理，也可以选取右子树中的最小值取代它并删除原结点。

理论上说，不论是选取左子树的最大值替代，还是右子树中的最小值替代，原树中序遍历的结果是一样的。