c - 递归如何在二叉搜索树中工作？

Question

二叉搜索树算法通常使用递归，我很难用它。

这是将树转换为其镜像的代码。

void mirror_image(struct tree* node1)
{
  if (node1==NULL)
    return;

  else
   {
      struct tree *temp;
      mirror_image(node1->left);
      mirror_image(node1->right);

       temp=node1->left;
       node1->left=node1->right;
       node1->right=temp;

    }

}

这是如何运作的？

Answer 1

基本上，您正在通过更改其左右节点来创建新树。指针，因为您正在更改地址。首先，您将左节点的值分配给临时指针变量。然后将右节点的值转换为左节点。最后 temp 中的值转移到右节点。就像交换一样。

Answer 2

因此，它使用扫描左子树

mirror_image(node1->left);

和右孩子的发辫使用

mirror_image(node1->right);

当到达终点时

if (node1==NULL)
    return;

它使用交换过程交换它们：

temp=node1->left;
node1->left=node1->right;
node1->right=temp;

我建议尝试使用一棵小二叉树，自己在纸上查看。