c++ - 二叉查找树左旋

Question

我将进行轮换，并尝试根据我调用的方法将进入我的二叉搜索树的类(class)向左或向右轮换。我的代码中某处有一个错误，我想我已经将它与旋转方法隔离开来，因为每次我在成功旋转后尝试打印时，它都会进入无限循环。我的方法中是否存在某种类型的指针或调用混淆？我觉得我的逻辑是正确的，但似乎无法弄清楚错误在哪里(或者即使它在这个方法中)。

这是我的左旋转方法:

bool BinarySearchTree::leftRotate(string number)
{
Course *x, *y;

if (treeSearch(number) == NULL){
    return false;
}
else{
    x = treeSearch(number);
}

if (x->getRight() == NULL){
    return false;
}
else{
    y = x->getRight();
    x->setRight(y->getLeft());
}

if (y->getLeft() != NULL){
    y->getLeft()->setParent(x);
}
y->getParent()->setParent(x);

if(x->getParent() == NULL){
    root = y;
}
else if( x->getParent()->getRight() == x){
    x->getParent()->setLeft(y);
}
else{
    x->getParent()->setRight(y);
}
    y->setLeft(x);
    x->setParent(y);
return true; 
}

提前致谢。

Answer 1

好像是

y->getParent()->setParent(x);

应该是

y->setParent(x->getParent());

但是在检查 x->getParent 是否为 NULL 之后执行此操作。

有点像

// Remove this line: y->getParent()->setParent(x);

if(x->getParent() == NULL){
    root = y;
}
else if( x->getParent()->getRight() == x){
    y->setParent(x->getParent());   // Insert this line
    x->getParent()->setLeft(y);
}

编辑:再次查看代码后，我认为即使 x->getParent() 返回 NULL，也应该调用 y->setParent(x->getParent())。原因是如果 y 成为新的根，y 也应该将 Parent 设置为 NULL。

所以下面的代码可能是更好的答案:

// Remove this line: y->getParent()->setParent(x);

y->setParent(x->getParent());   // Insert this line

if(x->getParent() == NULL){
    root = y;
}
else if( x->getParent()->getRight() == x){
    x->getParent()->setLeft(y);
}