隨機遞歸AVL樹高錯誤

我已經在這個程序上工作了好幾天了，現在已經完成了大部分工作。但是，調用遞歸高度函數時會出現隨機讀取訪問錯誤。爲了解決這個問題，我一直堅持了好幾個小時，我已經多次遍歷該函數進行計數，並且似乎無法找到該錯誤的模式。我試圖通過檢查null來解決這個問題，但由於我檢查的節點甚至不等於null，所以這也失敗了。這個錯誤中最混亂的部分是它是完全隨機的。這可能是一個簡單的修復，我只是看不到。任何幫助都是極好的。隨機遞歸AVL樹高錯誤

下面是代碼

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


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

這是我嘗試看看是否節點無效值。然而，這隻在有時候才起作用，因爲有時節點完全沒有價值。

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

讓我知道如果你需要任何其他細節

來源

2015-10-30 Giovanni

請不要修改代碼來修復錯誤，這會讓你的問題爲別人不太有用。另外請注意，您仍然遇到與其他調用高度的其他語句相同的問題。 –

做的最好的事情是通過它在調試步驟。然後你可以在每一點檢查樹，看看它出錯的地方。

這裏有幾件事情來看待：

你讓leftLink和rightLink使用new Node，但從來沒有釋放它們。請注意，您並不總是希望釋放它們，因爲它們有時指向有效的節點。你可能想重新思考這是如何工作的。

更重要的是，這條線：

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

從一個指針減去另一個高度後調用高度，你有你的括號混合起來。我想你的意思是

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

這可能會導致嚴重的問題。

（編輯爲清楚起見）

來源

2015-10-30 05:36:50

問題似乎總是發生在我檢查以查看我已傳遞到高度的節點是否包含有效數據的行。我不明白爲什麼無效節點正在通過。因爲錯誤是隨機的，就像在構建樹的過程中發生的那樣，很難找到它的發生時間或發生的方式。 – Giovanni

我突出顯示的那一行將傳遞一個無效指針，這會導致該問題。如果'height（leftLink）'是10，那麼你就調用'height（rightLink-10）'。 'rightLink - 10'不太可能是一個有效的指針。 –

它工作！起初它似乎沒有，但後來我注意到我在代碼中的不同點完成了完全相同的事情。修正了兩者，現在似乎運行良好。謝謝！ – Giovanni

隨機遞歸AVL樹高錯誤

回答

相關問題