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

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);//280
swap(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==belseb->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'spointerif(a->parent->left==a)a->parent->left=b;elsea->parent->right=b;if(b->parent->left==b)b->parent->left=a;elseb->parent->right=a;//swapchild'spointerif(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;}//swapthemselvespointerswap_p(&(a->parent),&(b->parent));swap_p(&(a->left),&(b->left));swap_p(&(a->right),&(b->right));}