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

Question

一个二叉树,普普通通的二叉树,结点是这样定义的:typedefstructnode_t{structnode_t*parent;structnode_t*left;structnode_t*right;intdata;}node;再简单不过了,现在递归创建一个二叉树.假设现在的二叉树是左边这样的,对调之后是右边这样的.11/\/\/\/\2383/\//\/456---->456/\/\9892//00要求一个函数voidswap(node*a,node*b),swap不能直接对调data://two和eight是内定的,不要在意这些细节printf("%d%d%d\n",two->data,eight->data,eight->right);//280swap(two,eight);printf("%d%d%d\n",two->data,eight->data,eight->right->data);//285求一个,多种/好的解法,算法小白真心求教...

Answer 1

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

voidswap_p(pTree*a,pTree*b){
pTreetmp;
tmp=*a;
*a=*b;
*b=tmp;
}
voidswap(pTreea,pTreeb){
pTreetmp_left,tmp_right,tmp_parent;
//swapparent'spointer
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;
//swapchild'spointer
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;
}
//swapthemselvespointer
swap_p(&(a->parent),&(b->parent));
swap_p(&(a->left),&(b->left));
swap_p(&(a->right),&(b->right));
}