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条回答

    报告相同问题?

    悬赏问题

    • ¥100 Jenkins自动化部署—悬赏100元
    • ¥15 关于#python#的问题:求帮写python代码
    • ¥20 MATLAB画图图形出现上下震荡的线条
    • ¥15 关于#windows#的问题:怎么用WIN 11系统的电脑 克隆WIN NT3.51-4.0系统的硬盘
    • ¥15 perl MISA分析p3_in脚本出错
    • ¥15 k8s部署jupyterlab,jupyterlab保存不了文件
    • ¥15 ubuntu虚拟机打包apk错误
    • ¥199 rust编程架构设计的方案 有偿
    • ¥15 回答4f系统的像差计算
    • ¥15 java如何提取出pdf里的文字?