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

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;
这是我的交换函数：（就像我说的，我认为问题不在这里，但您永远不知道）

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