2 a294153753 a294153753 于 2014.12.16 22:25 提问

关于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;
        }
    }
}
Csdn user default icon
上传中...
上传图片
插入图片