AVL二進制搜索樹的旋轉C++

我正在一個AVL樹上，我認爲我得到了一切正確的，但我不知道這裏是我的旋轉權函數，我正在糾正？AVL二進制搜索樹的旋轉C++

Node* BinaryTree::rotateRight(Node *N) 
{ 
    Node *newNode = new Node(); 
    newNode = N->getLeft(); 
    N->setLeft(newNode->getRight()); 
    newNode->setRight(N); 
    root = newNode; 
    return newNode; 
}

來源

2013-04-03 compprog254

那麼這將泄漏內存... – user1520427

我覺得你的代碼可能會造成內存泄漏後newNode = N->getLeft();

這是我實現我直接寫在這裏。你可以檢查它是否正確。我沒有測試過。

Node* BinaryTree::rotateRight(Node *N) 
{ 
    Node *newNode = new Node(); 
    Node *prevLeft = N->getLeft(); 

    prevLeft->setRight(newNode); 
    newNode->setLeft(prevLeft); 
    newNode->setRight(N); 
    N->setLeft(newNode); 

    root = newNode; 
    return newNode; 
}

來源

2013-04-03 06:52:35

我的作品，並沒有給我任何內存泄漏。按照你的建議。你將指針分配給N的左節點。同時給出了我的指示，這就是我應該這樣做的。 – compprog254

rotateRight不需要分配新節點。它僅通過操作指向現有節點的指針來工作。像這樣

Node* BinaryTree::rotateRight(Node *N) 
{ 
    Node *pivot = N->getLeft(); 
    N->setLeft(pivot->getRight()); 
    pivot->setRight(N); 
    return pivot; 
}

因此，除了不必要的分配新節點和分配給root用戶之外，你幾乎是正確的。

順便說一句，rotateRight通常可以做成靜態方法。

來源

2013-04-03 07:15:21 john

隨着你有它的方式，我得到一個內存泄漏，如果我只有一個樹的一面與一些信息。 – compprog254

我的代碼沒有分配任何內存（與你的不同）。如果你的代碼存在內存泄漏，那是因爲你的代碼中有其他地方存在bug。 – john

ive追蹤它的方法之前，我改變它像你的它很好，但現在它不does – compprog254

AVL二進制搜索樹的旋轉C++

回答

相關問題