完整的二叉树交换子级和父级错误

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++;
}
所以我这样构建测试：

int main(void)
{
    int *i1 = malloc(sizeof(int));
    int *i2 = malloc(sizeof(int));
    int *i3 = malloc(sizeof(int));
    int *i4 = malloc(sizeof(int));
    int *i5 = malloc(sizeof(int));
    int *i6 = malloc(sizeof(int));
    int *i7 = malloc(sizeof(int));
    int *i8 = malloc(sizeof(int));
    int *i9 = malloc(sizeof(int));
    int *i10 = malloc(sizeof(int));
    int *i11 = malloc(sizeof(int));
    int *i12 = malloc(sizeof(int));
    int *i13 = malloc(sizeof(int));
    int *i14 = malloc(sizeof(int));
    int *i15 = malloc(sizeof(int));
    *i1 = 1;
    *i2 = 2;
    *i3 = 3;
    *i4 = 4;
    *i5 = 5;
    *i6 = 6;
    *i7 = 7;
    *i8 = 8;
    *i9 = 9;
    *i10 = 10;
    *i11 = 11;
    *i12 = 12;
    *i13 = 13;
    *i14 = 14;
    *i15 = 15;

    CBTree * T  = newCBTree(); //create tree
    CBTreeInsert(T, (int*) i1);
    CBTreeInsert(T, (int*) i2);
    CBTreeInsert(T, (int*) i3);
    CBTreeInsert(T, (int*) i4);
    CBTreeInsert(T, (int*) i5);
    CBTreeInsert(T, (int*) i6);
    CBTreeInsert(T, (int*) i7);
    CBTreeInsert(T, (int*) i8);
    CBTreeInsert(T, (int*) i9);
    CBTreeInsert(T, (int*) i10);
    CBTreeInsert(T, (int*) i11);
    CBTreeInsert(T, (int*) i12);
    CBTreeInsert(T, (int*) i13);
    CBTreeInsert(T, (int*) i14);
    CBTreeInsert(T, (int*) i15);

    //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时，都会产生树损坏。