c - 这段C代码如何原位反转二叉树？

Question

我的老师要求我用 C 语言编写一个镜像二叉树的函数，我的意思是反转二叉树。我一直在努力解决这个问题，因为这个解决方案对我来说没有任何意义。我们使用的数据结构如下:

typedef struct nodo {

  int valor;

  struct nodo *esq, *dir;
} *ABin;

解决办法是:

void mirror (ABin *a) {

    ABin c = *a;
   if (c == NULL);

    else {
        ABin e = c -> esq;
        ABin d = c -> dir;
        c -> esq = d;
        c -> dir = e;
        mirror (&(c -> esq));
        mirror (&(c -> dir)); 
    }
}

这里我最关心的是是否使用指针。我不明白为什么，当我们递归调用该函数时，我们必须使用&当esq和dir已经指向struct nodo类型？

Answer 1

您问题的更高级别答案是，通过递归交换每个节点的左子树和右子树，您可以反转树的排序不变式。

通常，二叉搜索树维护这样的不变式:根据树的排序函数，每个左后代的排序早于(或等于)当前节点，而每个右后代的排序晚于(或等于)当前节点。通过交换树中每个节点的左子树和右子树，可以反转树的排序不变量。

至于您关于指针间接寻址级别的问题，镜像函数没有充分的理由采用 ABIN 指针。它应该只接受一个 ABIN，因为它是通过 typedef 指向树节点的指针。更好的是，如果没有充分的理由，您(或您的老师)首先不会为指向结构的指针创建 typedef。