C++ AVL樹重新計算高度

Question

即時通訊工作在一個AVL樹的implimentation，和我有重新計算高度函數的問題。當我調用它時，我傳入樹的根，並且具有值爲1的變量遍歷它，並發現一旦它進入while循環，就會如預期的那樣變形，但之後它將返回到只有一個變量。你可以看看它，看看我做錯了什麼。如果需要，我會發布更多的代碼，但我認爲只是該功能會爲您提供足夠的信息。謝謝

​​

Answer 1

您的函數應該計算二叉樹的每個子樹的高度，並將該值保存在該子樹的根節點中。您選擇遵循遞歸方法，這是標準方法。在這種方法中，必須首先計算左右子樹的高度，然後爲當前節點取最大值。

在您的實現中，您使用傳遞給參數的名爲count的值進行遞歸調用。鑑於我們需要從子節點中檢索一個計數，那麼這個值的目的是什麼，而不是傳遞給它們呢？

如果您：

• 從recalculate參數刪除值
• 已在recalculate方法首先調用自身的兩個孩子（如果適用）
• 使recalculate更新每個子節點高度當前節點的高度

你應該有它的工作。以下是基於此算法可能的實現：

void BinaryTree::recalculate(Node *leaf) { 
    int count = 0; 
    if (leaf == NULL) { 
     return; 
    } 
    if (leaf->getLeft() == NULL && leaf->getRight() == NULL) { 
     // no child, the height is 0 
     setHeight(0); 
     return; 
    } 
    if (leaf->getLeft() != NULL) { 
     recalculate(leaf->getLeft()); 
     count = leaf->getLeft()->getHeight(); 
    } 
    if (leaf->getRight() != NULL){ 
     recalculate(leaf->getRight()); 
     count = max(count, leaf->getRight()->getHeight()); 
    } 
    // include leaf in the height 
    setHeight(count+1); 
} 

如果無法使用getHeight方法，你可以通過具有recalculate返回它計算的高度替換它。