开发者社区> 问答> 正文

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

一个二叉树, 普普通通的二叉树, 结点是这样定义的:

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 0

swap(two, eight);
printf("%d %d %dn", two->data,

    eight->data,
    eight->right->data); // 2 8 5

求一个, 多种/好的解法, 算法小白真心求教...

展开
收起
a123456678 2016-06-07 16:39:20 2150 0
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
    赞同 展开评论 打赏
问答分类:
问答地址:
相关产品:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载