4

Great Tree-List Problem と呼ばれる興味深い問題に直面しました。問題は次のとおりです。

順序付けられた二分木では、各ノードには単一のデータ要素と、サブツリーへの「小さい」ポインタと「大きい」ポインタが含まれます。「小さい」サブツリーのすべてのノードは、親ノードのデータ以下です。 . 「大きな」サブツリー内のすべてのノードは、親ノードよりも大きいです。また、循環二重リンク リストは、前のポインターと次のポインターで構成されます。

問題は、順序付けられたバイナリ ツリーを取得し、内部ポインターを再配置して、そこから循環二重リンク リストを作成することです。「小さい」ポインタは「前」の役割を果たし、「大きい」ポインタは「次」の役割を果たす必要があります。リストは、ノードが昇順になるように配置する必要があります。再帰関数を作成する必要があります & 新しいリストへのヘッド ポインターを返します。

操作は O(n) 時間で実行する必要があります。

再帰がツリーを下ることは理解していますが、大小のサブツリーを再帰的にリストに変更する方法も、それらのリストを親ノードと一緒に追加する必要があります。

問題にどのようにアプローチすればよいですか?.. 問題を解決するための指示が必要です!.

4

3 に答える 3

2

再帰的プログラミングの鍵は、解決策が既にあると想像することです。

recLink(Tree t)したがって、ツリーへのポインターを受け取り、そのツリーを二重リンク循環リストに変換し、リストの先頭 (左端) ノードへのポインターを返す関数が既にあります。

recLink( n={Node: left, elt, right}) =  // pattern match tree to a full node
  rt := recLink( right);                // already
  lt := recLink( left);                 //   have it
  n.right := rt;       n.left := lt.left;        // middle node
  lt.left.right := n;  rt.left.right := lt;      // right edges
  lt.left := rt.left;  rt.left := n;      
  return lt;

エッジ ケース (空の子ブランチなど) で終了します。:)

于 2013-07-03T19:59:51.863 に答える