删除节点
删除一个BST的节点要比插入困难一点，但同样是要遵循一个原则，即：删除节点后仍然要保持“小-中-大”的逻辑关系。
假设要删除的节点是x，大体思路如下：
- 若要删除的节点小于根节点，则递归地在左子树中删除x
- 若要删除的节点大于根节点，则递归地在右子树中删除x
若要删除的节点恰好就是根节点，则分如下几种情况：
- a. 根节点若有左子树，则用左子树中最大的节点max替换根节点，并在左子树中递归删除max
- b. 否则，若有右子树，则用右子树中最小的节点min替换根节点，并在右子树中递归删除min
- c. 否则，直接删除根节点
代码：
typedef struct bst { //数据域 int data; //指针域 struct bst *lchild; struct bst *rchild; }BST, *pBST; //删除二叉树节点算法 pBST bstDelete(pBST root, int data) { if(root == NULL) return NULL; //0.如果想删除的节点小于根节点 if(data < root->data) { root->lchild = bstDelete(root->lchild, data); } //如果想删除的节点大于根节点 else if(data >root->data) { root->rchild = bstDelete(root->rchild, data); } //如果想删除的节点等于根节点 else { if(root->lchild != NULL) { pBST max; //找到左子树中最大的来替换删除的节点 for(max = root->lchild; max->rchild!=NULL; max = max->rchild); root->data = max->data; //再把左子树中最大的节点删掉 root->lchild = bstDelete(root->lchild, max->data); } else if(root->rchild != NULL) { pBST min; //找到右子树中最小的来替换删除的节点 for(min = root->rchild; min->lchild!=NULL; min = min->lchild); root->data = min->data; //再把右子树中最小的节点删掉 root->rchild = bstDelete(root->lchild, min->data); } else { return NULL; //删掉左（右）子树的最大（小）节点 } } }
