c++ - 随机递归AVL树高误差

Question

我已经为这个程序工作了好几天，并且大部分时间都可以正常工作。但是在调用递归高度函数时出现随机读取访问错误。我已经被困了几个小时试图修复这个错误，我已经通过这个函数太多次了，无法计数，而且似乎无法找到错误的模式。我试图通过检查是否为 null 来解决此问题，但由于我正在检查的节点甚至不等于 null，因此这也失败了。这个错误最令人困惑的部分是它是完全随机的。这可能是一个我看不到的简单修复。任何帮助都会很棒。

这是代码

int Tree::height(Node* p)
{
int left, right;


//if node is null return 0
if (p == nullptr || p == NULL)
{
    return 0;
}

这是我尝试查看节点是否具有无效值的地方。然而，这仅在某些时候有效，因为有时节点根本没有值(value)。

//if node has invalid values, return 0
if (p->getTheData() == NULL || p->getTheData() >= 1000000000 || p-    >getTheData() <= -1000000000)
{
    return 0;
}

这是在递归检查树时传入不存在的节点的地方。我不知道这是怎么发生的，也不知道为什么会发生这种情况

//recursively add to the height to check the balance
left = height(p->getLLink());
right = height(p->getRLink());

if (left > right)
    return left + 1;
else
    return right + 1;
}

这个函数最初是用来平衡树的。我传入节点，如果需要，它会平衡树。

void Tree::balFactor(Node* p, int inNodeData)
{
//declare needed objects and variables
int unBalancedRight = -2;
int two = 2;
Node* rightLink;
Node* leftLink;

//check to see if node is null and set a catch case
if (p == NULL || p->getRLink() == NULL)
{
    rightLink = new Node;
    rightLink->setBalFac(1001);
}
//if node is valid, move right
else
{
    rightLink = p->getRLink();
}

if (p == NULL || p->getLLink() == NULL)
{
    leftLink = new Node;
    leftLink->setBalFac(1001);
}

//if node is valid move
else
{
    leftLink = p->getLLink();
}

//check to see if the node is valid
if (p != nullptr)
{
    //check to see if the passed in node number is greater than the passed in data
    if (inNodeData > p->getTheData())
    {
        //check to see if the tree needs to be balanced
        if ((height(rightLink) - height(leftLink) == two))
        {
            //check to see what type of balancing needs to happen
            if (inNodeData > p->getRLink()->getTheData())
                rotateRightOnce(p);
            else
                rotateRightTwice(p);
        }
    }
    //check to see in incoming data is less than p node
    else if (inNodeData < p->getTheData())
    {
        //check to see if the data needs to be balanced
        if ((height(p->getLLink() - height(p->getRLink())) == two))
        {
            //check to see what type of rotation needs to happen
            if (inNodeData < p->getLLink()->getTheData())
                rotateLeftOnce(p);
            else
                rotateLeftTwice(p);
        }
    }

    //check the balance factor recursively until all nodes have been checked
    balFactor(p->getLLink(), inNodeData);
    balFactor(p->getRLink(), inNodeData);
}
}

如果您需要任何其他详细信息，请告诉我

Answer 1

最好的办法是在调试器中单步执行它。然后您可以在每个点检查树，看看哪里出了问题。

以下是一些需要注意的事项:

您使用 new Node 创建了 leftLink 和 rightLink，但从未释放它们。请注意，您并不总是希望释放它们，因为它们有时会指向有效节点。您可能需要重新考虑其工作原理。

更重要的是，这一行:

if ((height(rightLink - height(leftLink)) == two))

在从指针中减去另一个高度后调用高度，因为你的括号混淆了。我想你的意思是

if ((height(rightLink) - height(leftLink)) == two)

这可能会导致严重的问题。

(为清楚起见进行了编辑)