実際、私が知りたいのは、BST のインオーダー トラバーサル アルゴリズムを実装する方法ではなく、BST の挿入、削除、事前順序トラバーサル アルゴリズムのみを使用して実装する方法です。
挿入、削除、事前注文トラバーサルのための標準 BST アルゴリズムの実装が与えられていると想定できます。
2 に答える
0
うーん...ルートに+、左ノードに1、右ノードに2があるとしましょう。事前注文は次のように+ 1 2なり、順番は1 + 2..違いは、1番目と2番目が交換されていることです。したがって、挿入と削除がある場合は、各ルートノードの値を左側のノードの値と再帰的に交換してから事前注文を使用できます。戻るツリーをトラバースすると、順序どおりのトラバースが発生します。
これが進むべき道かどうかはわかりませんが、お役に立てば幸いです。
于 2011-10-18T05:46:45.353 に答える
0
私は解決策を見つけたと思います。:)
事前注文のトラバーサル、挿入、および削除メソッドがあります。
BST が与えられたとします。
私たちがしていることは、指定された BST を使用して事前注文トラバーサル メソッドを提供することです。事前注文トラバーサルは常に最初に親ノードに移動するため、ルートの左側のサブツリーが null になるまで、各ルート (ルートは最初に出会う親であるため) ノードを再帰的に削除および挿入します。
ここで、ノードがなくなるまでルートの削除を開始します。これらの削除されたノードを配列または必要な場所に配置します。ソートされたノードのセットを取得します。(つまり、ノードはソートされた順序で削除されます。最小のものから順に削除されます...)
于 2011-10-21T06:54:39.967 に答える