c - 二叉树镜像()这是如何工作的？

Question

虽然它看起来非常简单明了，但我在理解这段代码的核心方面确实遇到了一些困难。给定一个简单的二叉树，这个著名的函数会生成同一棵树的镜像结果。

void mirror(struct node* node) {
  if (node==NULL) {
    return;
  }
  else {
    struct node* temp;

    // do the subtrees
    mirror(node->left); //this part confuses me
    mirror(node->right); //so does this 

    // swap the pointers in this node
    temp = node->left;
    node->left = node->right;
    node->right = temp;
  }
}

这就是代码。阅读这段代码后，我有两个问题。

1. mirror(node->left) 和 mirror(node->right) 在调用栈上放置两个连续的函数调用。我的理解是，首先， 函数在左节点上调用，然后在右节点上调用。这个流程 只要节点为空，就会重复出现。但是当它不为空时 它返回？它是否只是返回调用语句而没有 返回任何东西？

2. 如何从调用堆栈调用这些函数？这将是 如果有人运行函数调用并告诉 我们如何以及为什么需要两次连续的函数调用。

附言:为什么不在此范围内使用迭代？

EDIT: quoting a useful comment by EOF, is it possible to tail-recurse this function by moving the swapping before the two recursive calls?

Answer 1

1. mirror(node->left) and mirror(node->right) places two consecutive function calls on the call stack.

这是一种奇怪的表达方式，它可能反射(reflect)出一种误解。从来没有一次调用堆栈包含这些函数调用的表示。两者。

My understanding is, first, the function is called on the left node and then right. This process recurs as long as node is empty. But when it is not empty what does it return?

该函数的类型为 void。它从不返回任何东西。

Does it just come back to the call statement without returning anything?

是的，当函数完成时，控制会继续执行函数调用后的下一条语句。

2. How are these functions invoked from the call stack?

函数不是从调用堆栈“调用”的。堆栈帧是为函数创建的，并作为调用函数过程的一部分进行推送。详细信息未指定；编译器负责生成代码以执行正确的操作。

It would be really helpful if someone runs through the function calls and tells how and why do we need two consecutive function calls.

镜像整棵树意味着反转每个节点的子节点。因此，在处理给定节点时，函数必须确保该节点的子节点都被镜像。它通过对每个执行递归调用然后交换它们来实现这一点。