佚名通过本文主要向大家介绍了二叉树结点计算,二叉树结点,完全二叉树结点计算,二叉树叶子结点算法,某二叉树共有7个结点等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
问题：二叉树结点位置对调的问题
描述:
解决方案1:
描述:
一个二叉树, 普普通通的二叉树, 结点是这样定义的:
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
求一个, 多种/好的解法, 算法小白真心求教...
解决方案1:
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));
}
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;
}