a294153753 2014-12-16 14:25
浏览 889

关于AVL平衡树删除,删除根节点出问题

 void Cstree::deleteuser(string na)
{
    while (!path.empty())
    {
        path.pop();
    }
    bool flag;
    Cnode* t;
    Cnode* parent;
    deletehelp(na, flag, t, parent);
    if (!flag) //没有找到要删除的用户
    {
        cout << "用户名不存在,删除失败!" << endl;
        getchar();
        return;
    }
    if (t->left != NULL && t->right != NULL) //要删除的节点有左右节点
    { 
        Cnode* temp = t->right; 
        parent = t;
        while (temp->left != NULL)
        { 
            path.push(temp);
            parent = temp;
            temp = temp->left;
        }
        t->name = temp->name; //交换被删节点与其后继节点的用户名与密码
        t->password = temp->password;
        t = temp;
    }
    Cnode* childtree = t->left; //指向t的子树的指针
    if (childtree == NULL)
    {
        childtree = t->right; //若左节点不存在,则指向右节点(右节点也可能为NULL)
    }
    if (parent == NULL) //删除的是根节点
    {
        root = childtree;
    }
    else if (parent->left == t) //若t是parent的左节点
    {
        parent->left = childtree; //则parent的左指针指向childtree
    }
    else //若t是parent的右节点
    {
        parent->right = childtree; //则parent的右指针指向childtree
    }
    string username = t->name;
    delete t;
    while (!(path.empty())) //删除完成,修改平衡因子,旋转
    {
        Cnode* location = path.top(); //从删除位置开始,逐层向上修改平衡因子,需要弹出栈中元素
        if (username > location->name) //删除的是左子树中的节点
        {
            (location->balanceFactor)++;
        }
        else if (username < location->name) //删除的是右子树中的节点              
        {
            (location->balanceFactor)--;
        }
        int bF = location->balanceFactor; //修改后的平衡因子
        path.pop(); //删除栈顶元素
        if (bF != 0)
        { 
            if (bF == 1 || bF == -1) //平衡因子为1或-1时说明删除后的树还是平衡的,不需要旋转
            {
                return;
            }
            else if (bF == 2 || bF == -2) //如果为2或-2,则进行旋转
            {
                rotation(bF, location);
            }
        }
    }
    cout << "删除成功!" << endl;
    getchar();
}
 void Cstree::deletehelp(string name, bool &flag, Cnode* &location, Cnode* &parent)
{
    location = root;
    parent = NULL;
    flag = false;
    while (!flag && location != NULL)
    {
        if (name < location->name)
        {
            path.push(location);
            parent = location;
            location = location->left;
        }
        else if (location->name < name)
        {
            path.push(location);
            parent = location;
            location = location->right;
        }
        else //找到要删除的节点
        {
            flag = true;
        }
    }
}
  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 求差集那个函数有问题,有无佬可以解决
    • ¥15 【提问】基于Invest的水源涵养
    • ¥20 微信网友居然可以通过vx号找到我绑的手机号
    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名
    • ¥65 汇编语言除法溢出问题