完成二叉树交换子和父错误

Question

我正在为学校做一个项目，但遇到了一个奇怪的错误。我正在实现一个完整的二叉树，但我在与他的父节点交换节点时遇到了问题。

在我的测试过程中，我发现有 1 个案例无法正常工作。

这个：

除那种情况外，其他所有交换都工作正常

我的树结构是这样的

typedef struct TreeNode {
    void * data;
    struct TreeNode * left;
    struct TreeNode * right;
    struct TreeNode * parent;
} TNode;

typedef struct CompleteBinaryTree {
    TNode * root;
    TNode * last;
    int numelm;
} CBTree;

CBTree * newCBTree(void)
{
    CBTree * ret = malloc(sizeof(CBTree));

    if( ret )
    {
        ret->root = NULL;
        ret->last = NULL;

        ret->numelm = 0;
    }
}

TNode * newTNode( void * data )
{
    TNode *ret = malloc(sizeof(TNode));
    if( ret )
    {
        ret->data = data;
        ret->parent = ret->left = ret->right = NULL;
    }

    return ret;
}

这是我的交换函数：

void CBTreeSwap(CBTree* tree, TNode* parent, TNode* child)
{
  assert(parent != NULL && child != NULL && (child == parent->left || child == parent->right));

  if (child == tree->last)
    tree->last = parent;

  if(child == parent->left)
  {        
    if(child->left != NULL)
      child->left->parent = parent;

    parent->left = child->left;
    child->left = parent;

    if (child->right != NULL)
      child->right->parent = parent;

    if (parent->right != NULL)
      parent->right->parent = child;

    TNode * tmp = child->right;
    child->right = parent->right;
    parent->right = tmp;

    if (parent != tree->root)
    {
      parent->parent->left = child;
      child->parent = parent->parent;
      parent->parent = child;
    }
    else
    {
      child->parent = NULL;
      tree->root = child;
      parent->parent = child;
    }
  }
  else
  {
    if(child->right != NULL)
      child->right->parent = parent;

    parent->right = child->right;
    child->right = parent;

    if(child->left != NULL)
      child->left->parent = parent;

    if(parent->left != NULL)
      parent->left->parent = child;

    TNode * tmp = child->left;
    child->left = parent->left;
    parent->left = tmp;

    if(parent != tree->root)
    {
      parent->parent->right = child;
      child->parent = parent->parent;
      parent->parent = child;
    }
    else
    {
      child->parent = NULL;
      tree->root = child;
      parent->parent = child;
    }
  }
}

要插入树中使用这个：

void CBTreeInsert(CBTree* tree, void* data)
{
  TNode * tmp = newTNode(data);
  TNode * curr = tree->last;

  if(tree->root == NULL)
  { //empty
    tree->root = tmp;
  }
  else if(tree->last == tree->root)
  { //one node
    tree->last->left = tmp;
    tmp->parent = tree->root;
  }
  else if(tree->last->parent->right == NULL)
  { //general
    tree->last->parent->right = tmp;
    tmp->parent = tree->last->parent;
  }
  else if (tree->last == tree->last->parent->right)
  { //degenarated
    curr = tree->last->parent ;

    while (1)
    {
      if (curr == tree->root)
        break ;

      if (curr == curr->parent->left)
      {
        curr = curr->parent->right ;
        assert(curr != NULL) ;
        break ;
      }
      curr = curr->parent ;
   }

   while (curr->left != NULL) 
   {
      assert(curr->right != NULL) ;
      curr = curr->left ;
   }
    assert(curr->right == NULL) ;
    tmp->parent = curr ;
    curr->left  = tree->last = tmp;
  }
  else 
  {
    fprintf(stderr,"Error\n");
  }
  tree->last = tmp;
  tree->numelm++;
}

所以我这样构建我的测试：

void main(){
  int * i[15], j;

  CBTree * tree  = newCBTree(); //create tree

  for(j=0; j<15; j++)
  {
    i[j] = malloc(sizeof(int));
    *(i[j]) = j+1;

    CBTreeInsert(tree, (int*) i[j]);
  }

    //All these work
    CBTreeSwap(T, T->root->left, T->root->left->left);
    CBTreeSwap(T, T->root, T->root->left);
    CBTreeSwap(T, T->root->right, T->root->right->right);
    CBTreeSwap(T, T->root, T->root->right);
    CBTreeSwap(T, T->last->parent, T->last);

    //This one is broken
    CBTreeSwap(T, T->root->left, T->root->left->right);
}

当我运行那个失败的测试并试图查看我的树时，我得到了我的树的所有分支，然后是段错误。

这只是一个更大项目的一部分，如果您需要我的更多代码，请随时询问

谢谢！

Answer 1

你的问题不仅在 T->left 和 T->left->right 交换时（损坏所有 T->left 左边的子树）而且在 T->right 和 T->right->left 被交换。

问题出在 CBTreeSwap() 函数中。

它的实现其实很棘手。理解它并不容易，所以我会提出我的实现。我只能说问题的根源可能是在某个地方，在交换过程中，您分配了 parent/child 的某些字段，而没有注意它们已经被更改！

修复

请在下面找到 CBTreeSwap() 的更正版本。 child 是 parent->left 或 parent->right 的情况之间的区别是正确的，但是在这两种情况下许多其他操作是常见的。代码有注释。

void CBTreeSwap(CBTree* tree, TNode* parent, TNode* child)
{
    assert(parent != NULL && child != NULL && (child == parent->left || child == parent->right));

    if (child == tree->last)
        tree->last = parent;

    /* Save child's childs */
    TNode *tmpL = child->left, *tmpR = child->right;

    /* Link child (new parent!) to parent's parent */
    if(parent != tree->root)
    {
        TNode *parpar = parent->parent;
        child->parent = parpar;

        /* Is parent left or right child of his parent? */
        if( parent->parent->left == parent)
          parpar->left = child;
        else
          parpar->right = child;
    }
    else
    {
        child->parent = NULL;
        tree->root = child;
    }

    /* In order to actually swap nodes we need to know if child is at parent's left or right*/       
    if(child == parent->left)
    {        
        /* Link parent's other child to child */
        parent->right->parent  = child;
        child->right  = parent->right;

        /* Link former parent to child's right (making it its new right child) */
        child->left = parent;
        parent->parent = child;
    }
    else /* child == parent->right */
    {
        /* Link parent's other child to child */
        parent->left->parent  = child;
        child->left  = parent->left;

        /* Link former parent to child's right (making it its new right child) */
        child->right = parent;
        parent->parent = child;
    }

    /* Link child's childs to former parent */
    parent->left  = tmpL;
    parent->right = tmpR;
    if(tmpL != NULL)
        tmpL->parent = parent;
    if(tmpR != NULL)
        tmpR->parent = parent;
}

所以：

保存 child 的 child。
Linkchild（新parent）到旧parent的parent，管理parent的情况根节点。我们需要了解 parent 是在他的 parent.
将parent和child按照原来的相互位置交换。如果我们出错了，我们可能会破坏整个子树。
恢复 child 的 childs

我测试了上面的代码，它按预期工作。

PS：虽然与本题无关，但考虑使用数组和循环进行初始化。下面的代码就像您的初始化一样。是不是更优雅？

  int * i[15], j;

  CBTree * tree  = newCBTree(); //create tree

  for(j=0; j<15; j++)
  {
    i[j] = malloc(sizeof(int));
    *(i[j]) = j+1;

    CBTreeInsert(tree, (int*) i[j]);
  }

另一种解决方案

但是有一个更简单的解决方案可以实现您的特定目标：为什么要交换整个子树，而在程序结束时，只需要节点 contents交换了？

所以你的交换函数变成：

void CBTreeSwap(CBTree* tree, TNode* parent, TNode* child)
{
    assert(parent != NULL && child != NULL && (child == parent->left || child == parent->right));

    void *tmpData = parent->data;
    parent->data = child->data;
    child->data = tmpData;
}

完成二叉树交换子和父错误

Complete Binary Tree swapping child and parent bug

c

swap

binary-tree

pointers

segmentation-fault

修复

另一种解决方案