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;
}
}
}