recursion - 再帰が不規則な BST トラバーサルでどのように機能するかを誰かが説明できますか?

Question

インオーダートラバーサルのコードは次のようになります

  if left[x] != NULL
    recurse left
    process
  right[x] !=NULL
    recurse right

すべてをコーディングしましたが、正常に動作します。その後、私はもっと考え始め、プロセスを考えすぎて、再帰が実際にどのように機能するかについて迷っています。ずっと左だと思うので、両方のノードがnullであるため、再帰は終了します。

私がずっと左にいて、左右のノードの両方が NULL である場合、再帰呼び出しによってどのように親ノードに戻ってトラバーサルを続けることができますか?

Answer 1

current_nodeすべての再帰*と同様に、再帰呼び出しが戻り始めると、呼び出しスタックには操作の制御が含まれます。プログラム制御は、再帰呼び出しを行う前に調べていた親にポインターが設定されているポイントに戻ります。

(* 末尾呼び出しの最適化が行われていない限り、すべての再帰。その場合は単なるループです)。