0

我现在正在寻找一种方法，它给了我给定树的所有路径。想象一下下面的树：

A
  B
  C
    D
      E
    F
  G

现在我想将所有路径作为单独的字符串：

  • AB
  • ACDE
  • ACF
  • 股份公司

- - - - - - - -更新 - - - - - - - - -

正如评论中已经提到的，我正在寻找所有的树路径而不是子树。我找到了以下解决方案，但我不确定它是否会是一个好的解决方案：

  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

您可以使用 BFS 算法（Wikipedia 上解释的图形算法），从要创建根的节点开始。

该算法的行为如下：

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 回答
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

一个，ac，aca

a,ac,acb

一个，ac，acc，acca

a,ac,acc,accb

一个，ac，acc，accc

一个，广告

于 2017-08-15T19:05:00.670 回答