如何在二叉树中交换两个节点 [英] How to swap two nodes in binary tree

问题描述

在我的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;
  }

它需要两个节点指针并交换它们。但当我调用此函数时，它会出现内存冲突错误。我在这里做错了什么？如果您知道交换二叉树中两个节点的任何其他简单方法，请分享。

推荐答案

此问题比看起来复杂，因为涉及树根的特殊情况，当一个是另一个的父项时交换两个项，并修复左子项和右子项的父指针。以下是一些工作正常的代码。我想可以在某种程度上把它做得更整洁、更短。

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

这篇关于如何在二叉树中交换两个节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！