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;

小さな二分木で試してみることをお勧めします。紙の上で自分で見てください。