13_学习日志_数据结构_二叉排序树的删除

#include<吾亦澹荡人，拂衣可同调>

1.介绍

        遍历排序树，复用上节建树代码。

2.删除节点子函数

        首先判断是否为空树，直接返回。比被删节点值大便向向左递归继续寻找，反之则向右递归，递归到NULL的节点直接返回，说明删除失败。对找到被删节点再做分支判断，该节点若是左节点为空，则右节点顶替被删节点位置，反之则左边替代。还有一种情况，此时被删节点左右都不为空，则需要找到左边所有树最大的节点或者右边所有树最小的节点，即为左树最右节点或右树最左节点，这里选择右树最左节点，首先将p指向右边子树们的根节点，左子树不为空时就不停向左遍历，将值赋给最初的根节点之后，递归调用删除被借用的节点。

void del_tree(BiNode &t,int key){
    if(t==NULL){
        return;
    }
    if(t->data>key){
        del_tree(t->lchild,key);
    }else if(t->data<key){
        del_tree(t->rchild,key);
    }else{
        if(t->rchild==NULL){
            t=t->lchild;
        }else if(t->lchild==NULL){
            t=t->rchild;
        }else{
            BiNode p=t->rchild;
            while (p->lchild){
                p=p->lchild;
            }
            t->data=p->data;
            del_tree(t->rchild,p->data);
        }
    }
}

3.总结

        递归能够节省代码量，但是理解起来会相对困难，可以理解为，根节点的左子树节点同样也可以成为根节点，循环往复，每个被删节点都可以成为根节点，只是操作上有所不同，有的操作会被省略，递归写出可以让所有节点执行一遍的过程。