二叉树结点位置对调的问题
一个二叉树, 普普通通的二叉树, 结点是这样定义的:
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
求一个, 多种/好的解法, 算法小白真心求教...
我不是兔子
10 years, 2 months ago
Answers
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));
}
蜷成一坨面包
answered 10 years, 2 months ago
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;
}
stillzz
answered 10 years, 2 months ago
下面的代码是错的, 没有考虑a的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);
}
westl
answered 10 years, 2 months ago