5

ツリーの葉へのすべてのパスを検索する関数を作成しようとしています。たとえば、次のようなツリーがあるとします。

           1
         /  \
        2    5
       / \    \
      3   4    6

出力リストは次のようになります[[1,2,3],[1,2,4],[1,5,6]]。

この関数の型アノテーションは次のとおりbranches :: Tree a -> [[a]]です。これはData.Treeパッケージで定義されたTreeタイプを使用し、サンプルツリーはバイナリですが、実際のツリータイプはバラの木であることに注意してください。

4

3 に答える 3

3

単純な関数：

listtree :: [a] -> Tree a -> [[a]]
listtree l (Node a []) = [l++[a]]
listtree l (Node a forest) = concatMap (listtree (l++[a])) forest

リストを使用してルートから現在のノードへのパスを記録し、現在のノードのラベルをパスに追加してから、listtree各サブノードに再帰的にマップします。

listtree [] (Node 1 [(Node 2 [(Node 3 []), (Node 4 [])]), (Node 5 [(Node 6 [])])]))

望ましい結果を得る[[1,2,3],[1,2,4],[1,5,6]]

于 2013-03-11T14:30:29.370 に答える
1

部分パスリストの前に新しいラベルを追加し、出力用にそれらを逆にすることで、パスを作成します。

listtree tree = map reverse $ traverse [] tree
  where traverse path (Node label []) = [label:path]
        traverse path (Node label xs) = concat $ map (traverse (label:path)) xs

リストの最後ではなく先頭にラベルを追加する理由は、追加には時間と割り当てられたメモリにO（N）がかかり、ヘッドの追加にはO（1）がかかるためです。もちろん、リストの反転もO（N）ですが、反転はリストごとに1回だけ実行されます...

したがって、上記の「頭に追加し、必要に応じて逆にする」パターンは、機能的なアルゴリズムやデータ構造を使用する場合に広く使用されているイディオムです。

編集：@luquiのコメントから、パスを取得するための補完的な方法は、パスを下から上に構築することです。

listtree (Node label []) = [[label]]
listtree (Node label xs) = map (label:) $ concat $ map listtree xs

これは私のソリューションよりも短く（そしておそらくより明確で）、パスを希望の順序で提供するという追加の利点があります。パスはルートではなくリーフから開始されます。

（前のソリューションと同様に）パスリストは、リストの最後に追加するのではなく、リストの最初にヘッドを追加することによって拡張されることに注意してください。

于 2013-03-11T17:27:55.163 に答える
0

それは簡単です...これらはあなたが心に留めておく必要があることです：-

  1. 関数を再帰的に呼び出す
  2. 関数内では、トラバーサルはPreOrder（ルート、左、右）の形式である必要があります。
  3. 再帰関数内で配列を使用し、アクセスしたすべてのノードの値を格納します。
  4. 訪問したノードがリーフの場合...ノード->左==NULLおよびノー​​ド->右==NULL。次に、配列の内容を出力します。
于 2013-03-11T04:31:52.603 に答える