c - 再帰またはスタックを使用しないツリーのPostOrderトラバーサル

Question

重複の可能性：
再帰なしのバイナリツリーのポストオーダートラバーサル

私はモリスによる二分木でインオーダートラバーサルアルゴリズムを実行していました。postorder再帰とスタックを使用せずにトラバースする方法があるかどうかを誰かに提案できますか？

Answer 1

これは、スレッドツリーを使用して行うことができます。メソッドの概要は次のとおりです（ここから取得—スライド31を参照）。

• ポストオーダー：ルートを左の子孫として持つダミーノードが作成されました。
• 変数を使用して、現在のアクションのタイプを確認できます。
• アクションが左トラバーサルであり、現在のノードに左子孫がある場合、子孫がトラバースされます。それ以外の場合、アクションは右トラバーサルに変更されました。
• アクションが右トラバーサルであり、現在のノードに左子孫がある場合、アクションは左トラバーサルに変更されます。それ以外の場合、アクションはノードへのアクセスに変更されました。
• アクションがノードを訪問している場合：現在のノードが訪問された後、そのポストオーダーサクセサを見つける必要があります。
• スレッドを介して現在のノードの親にアクセスできる場合（つまり、現在のノードが親の左の子である場合）、トラバーサルは親の右の子孫で続行するように設定されます。
• 現在のノードに右の子孫がない場合、これはノードの右に拡張されたチェーンの終わりです。
• 最初：チェーンの先頭には、現在のノードのスレッドを介して到達します。
• 2番目：チェーン内のノードの正しい参照が逆になります。
• 最後に、チェーンが逆方向にスキャンされ、各ノードにアクセスしてから、正しい参照が以前の設定に復元されます。

上記の参照が示すように、ツリー構造に一時的な変更を使用する場合は、スレッド化せずに実行することもできます。