二叉树结点位置对调的问题
一个二叉树, 普普通通的二叉树, 结点是这样定义的:
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 %dn", two->data,
eight->data,
eight->right); // 2 8 0swap(two, eight);
printf("%d %d %dn", two->data,
eight->data,
eight->right->data); // 2 8 5求一个, 多种/好的解法, 算法小白真心求教...
展开
收起
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; }2019-07-17 19:30:28赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
