如何交換兩個節點在二叉樹

Question

在我的BST類我使用下面的函數來交換兩個節點

void swapNodes(BSTNode *node1, BSTNode *node2) 
    { 
    if(node1->parent->left==node1) 
     node1->parent->left = node2; 
    else 
     node1->parent->right = node2; 
    if(node2->parent->left==node2) 
     node2->parent->left = node1; 
    else 
     node2->parent->right = node1; 

    BSTNode *temp; 
    temp->parent = node1->parent; 
    temp->left = node1->left; 
    temp->right = node1->right; 

    node1->parent = node2->parent; 
    node1->left = node2->left; 
    node1->right = node2->right; 

    node2->parent = temp->parent; 
    node2->left = temp->left; 
    node2->right = temp->right; 
    } 

它需要兩個節點指針和交換他們兩個。但是當我調用這個函數時會出現內存違規錯誤。我在這裏做錯了什麼？如果你知道任何其他簡單的方法來交換二叉樹中的兩個節點，請分享。

Answer 1

BSTNode *temp; 

未初始化

Answer 2

這個問題要複雜得多，似乎是因爲涉及樹的根特殊情況下，交換兩個項目時，其中一個是另一個的父母，並固定了父指針左邊和右邊的兒童項目。這是一些有用的代碼。我懷疑它可能會以某種方式變得更整潔，更短。

void Swap(T* aP,T* aQ) 
    { 
    T* new_p_parent = aQ->iParent; 
    T* new_p_left = aQ->iLeft; 
    T* new_p_right = aQ->iRight; 
    T** new_p_link = &iRoot; 
    if (aQ->iParent) 
     new_p_link = aQ->iParent->iLeft == aQ ? &aQ->iParent->iLeft : &aQ->iParent->iRight; 

    T* new_q_parent = aP->iParent; 
    T* new_q_left = aP->iLeft; 
    T* new_q_right = aP->iRight; 
    T** new_q_link = &iRoot; 
    if (aP->iParent) 
     new_q_link = aP->iParent->iLeft == aP ? &aP->iParent->iLeft : &aP->iParent->iRight; 

    if (aQ->iParent == aP) 
     { 
     new_p_parent = aQ; 
     new_p_link = nullptr; 
     if (aP->iLeft == aQ) 
      new_q_left = aP; 
     else 
      new_q_right = aP; 
     } 
    else if (aP->iParent == aQ) 
     { 
     new_q_parent = aP; 
     new_q_link = nullptr; 
     if (aQ->iLeft == aP) 
      new_p_left = aQ; 
     else 
      new_p_right = aQ; 
     } 

    aP->iParent = new_p_parent; 
    aP->iLeft = new_p_left; 
    if (aP->iLeft) 
     aP->iLeft->iParent = aP; 
    aP->iRight = new_p_right; 
    if (aP->iRight) 
     aP->iRight->iParent = aP; 
    if (new_p_link) 
     *new_p_link = aP; 

    aQ->iParent = new_q_parent; 
    aQ->iLeft = new_q_left; 
    if (aQ->iLeft) 
     aQ->iLeft->iParent = aQ; 
    aQ->iRight = new_q_right; 
    if (aQ->iRight) 
     aQ->iRight->iParent = aQ; 
    if (new_q_link) 
     *new_q_link = aQ; 
    }