二叉树结点位置对调的问题

Question

一个二叉树, 普普通通的二叉树, 结点是这样定义的:

typedef struct node_t {
    struct node_t* parent;
    struct node_t* left;
    struct node_t* right;

    int data;
} node;

再简单不过了, 现在递归创建一个二叉树. 假设现在的二叉树是左边这样的, 对调之后是右边这样的.

     1                    1
    / \                  / \
   /   \                /   \
  2     3              8     3
 / \   /              / \   /
4   5 6     ---->    4   5 6   
   / \                  / \
  9   8                9   2
 /                    /
0                    0

要求一个函数 void swap(node* a, node* b), swap不能直接对调data:

// two和eight是内定的, 不要在意这些细节
printf("%d %d %d\n", two->data,
        eight->data,
        eight->right); // 2 8 0
swap(two, eight);
printf("%d %d %d\n", two->data,
        eight->data,
        eight->right->data); // 2 8 5

求一个, 多种/好的解法, 算法小白真心求教...

Answer 1

void swap(node* a, node* b)
{
    // 处理a与b相邻的情况，
    // 基本思路：将a指向b的邻边指向自己，将b指向a的邻边指向自己，交换的时候就不会出错
    if (a->left == b){
        a->left = a;
        b->parent = b;
    }
    else if (a->right == b){
        a->right = a;
        b->parent = b;
    }
    else if (a->parent == b) {
        a->parent = a;
        if (b->left == a)
            b->left == b
        else
            b->right == b;
    }

    node* tmp = b->parent;
    b->parent = a->parent;
    a->parent = tmp;
    tmp = b->right;
    b->right = a->right;
    a->right = tmp;
    tmp = b->left;
    b->left = a->left;
    a->left = tmp;
}

Answer 2

void swap_p( pTree *a, pTree *b){
    pTree tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void swap(pTree a, pTree b){
    pTree tmp_left,tmp_right,tmp_parent;

    //swap parent's pointer
    if( a->parent->left == a)
        a->parent->left = b;
    else
        a->parent->right = b;

    if( b->parent->left == b)
        b->parent->left = a;
    else
        b->parent->right = a;

    //swap child's pointer
    if( a->left != NULL){
        a->left->parent = b;
    }
    if( a->right != NULL){
        a->right->parent = b;
    }

    if( b->left != NULL){
        b->left->parent = a;
    }
    if( b->right != NULL){
        b->right->parent = a;
    }

    //swap themselves pointer
    swap_p( &(a->parent), &(b->parent));
    swap_p( &(a->left), &(b->left));
    swap_p( &(a->right), &(b->right));
}

Answer 3

下面的代码是错的, 没有考虑a, b的parent,child节点的指针. 有时间再改把

---

先交换,　再事后处理异常情况　也是一条思路.　检查a,b的left, right, 如果指向了自身, 则知a,b相邻. 把指针重新指向另一个节点即可.

void swap_ptr(node **p1, node **p2)
{
    node *tmp;
    tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

#define CORRECT_SELF_POINT(a, ptr, b) do {  \
    if(((a)->ptr) == (a)){                  \
        ((a)->ptr) = (b);                   \
        (b)->parent = (a);                  \
        return;                             \
    }                                       \
} while(0)

void swap(node *a, node *b){
    swap_ptr(&(a->parent),   &(b->parent));
    swap_ptr(&(a->left),     &(b->left));
    swap_ptr(&(a->right),    &(b->right));

    CORRECT_SELF_POINT(a,   left,     b);
    CORRECT_SELF_POINT(a,   right,    b);
    CORRECT_SELF_POINT(b,   left,     a);
    CORRECT_SELF_POINT(b,   right,    a);
}