0

特定のツリーのすべてのパスを取得できるメソッドをしばらく探しています。次のツリーを想像してください。

A
  B
  C
    D
      E
    F
  G

今、私はすべてのパスを別の文字列として取得したい:

  • AB
  • ACDE
  • ACF
  • AG

- - - - - - - -アップデート - - - - - - - - -

コメントで既に述べたように、サブツリーではなくすべてのツリーパスを探しています。次の解決策を見つけましたが、それが良い解決策になるかどうかはわかりません。

  private ArrayList<ArrayList<String>> abstractProperties;

    ........

    getTreePath(abstractHw, new ArrayList<String>());

.......

    private void getTreePath(Node hw, ArrayList<String> path) {
        path.add(hw.getName());
        if (hw.getNodes().isEmpty()) {
            abstractProperties.add(path);
        } else {
               for (Node subHw : hw.Nodes()) {
                getTreePath(subHw, new ArrayList<String>(path));
               }
            }
    }

どう思いますか？

4

3 に答える 3

0

これは、任意のツリー構造でリーフ ノードへのフル パスを出力する方法です。

<script>
    function factory(name, children) {
        return {
            name: name,
            children: children
        }
    }

    var paths = [];

    function getGroupPaths(node, path) {
        path.push(node.name);
        if (node.children.length == 0) {
            console.log(path.join());
        } else {
            for (child of node.children) {
                getGroupPaths(child, path);
            }
        }
        path.pop();
    }

    var acca = factory('acca', []);
    var accb = factory('accb', []);
    var accc = factory('accc', []);
    var aca = factory('aca', []);
    var acb = factory('acb', []);
    var acc = factory('acc', [acca, accb, accc]);
    var aa = factory('aa', []);
    var ab = factory('ab', []);
    var ac = factory('ac', [aca, acb, acc]);
    var ad = factory('ad', []);
    var a = factory('a', [aa, ab, ac, ad]);

    var path = [];
    getGroupPaths(a, path);
</script>

そして結果：

ああ、ああ

a,ab

a,ac,aca

a,ac,acb

a,ac,acc,acca

a、ac、acc、accb

a,ac,acc,accc

、広告

于 2017-08-15T19:05:00.670 に答える
0

ルートにしたいノードから始めて、BFS アルゴリズム (ウィキペディアで説明されているグラフ アルゴリズム) を使用できます。

アルゴリズムは次のように動作します。

procedure BFS(G,v,btree):
      create a queue Q
      enqueue v onto Q
      mark v
      btree = new Tree(v);//Create a tree structure with v as root
      while Q is not empty:
          t ← Q.dequeue()
          btree.add(t) // Here its where you add elements to your tree
          for all edges e in G.incidentEdges(t) do
             o ← G.opposite(t,e)
             if o is not marked:
                  mark o
                  enqueue o onto Q

Q が空の場合、考えられるすべてのノードを処理し、それらすべてがバイナリ ツリー (btree) に追加されたことを意味します。

btree を取得したら、単純なアルゴリズムを適用して必要なものを取得できます

于 2013-11-19T18:54:55.787 に答える
0

ツリー (より正確にはノード) の実装は、子があるかどうかに関係なく返すことができる必要があります。

より詳細な回答が必要な場合は、試したことと、ツリーをどのように保存しているかを示してください。

于 2013-11-19T18:56:52.550 に答える