文字列パスのリストからツリー構造を構築します

StackOverflow https://stackoverflow.com/questions/1005551

  •  05-07-2019
  •  | 
  •  

質問

["x1 / x2 / x3"、 "x1 / x2 / x4"、 "x1 / x5"]などの文字列パスのリストがリストにあります。 このリストからツリーのような構造を構築する必要があります。この構造を繰り返して、きれいに印刷されたツリーを取得できます。 このように

     x1
    /  \
   x5   x2
       /  \
      x3  x4

アイデア/提案はありますか？ 文字列のリストを処理することで最初に問題を攻撃できると思います編集：選択した正しい答えはエレガントな実装でしたが、他の提案も良かったです。

役に立ちましたか？

解決

訪問可能なツリーの単純な実装の実装に従います：

class Tree<T> implements Visitable<T> {

    // NB: LinkedHashSet preserves insertion order
    private final Set<Tree> children = new LinkedHashSet<Tree>();
    private final T data;

    Tree(T data) {
        this.data = data;
    }

    void accept(Visitor<T> visitor) {
        visitor.visitData(this, data);

        for (Tree child : children) {
            Visitor<T> childVisitor = visitor.visitTree(child);
            child.accept(childVisitor);
        }
    }

    Tree child(T data) {
        for (Tree child: children ) {
            if (child.data.equals(data)) {
                return child;
            }
        }

        return child(new Tree(data));
    }

    Tree child(Tree<T> child) {
        children.add(child);
        return child;
    }
}

訪問者パターンのインターフェース：

interface Visitor<T> {

    Visitor<T> visitTree(Tree<T> tree);

    void visitData(Tree<T> parent, T data);
}

interface Visitable<T> {

    void accept(Visitor<T> visitor);
}

訪問者パターンのサンプル実装：

class PrintIndentedVisitor implements Visitor<String> {

    private final int indent;

    PrintIndentedVisitor(int indent) {
        this.indent = indent;
    }

    Visitor<String> visitTree(Tree<String> tree) {
        return new IndentVisitor(indent + 2);
    }

    void visitData(Tree<String> parent, String data) {
        for (int i = 0; i < indent; i++) { // TODO: naive implementation
            System.out.print(" ");
        }

        System.out.println(data);
    }
}

そして最後に（!!!）簡単なテストケース：

    Tree<String> forest = new Tree<String>("forest");
    Tree<String> current = forest;

    for (String tree : Arrays.asList("x1/x2/x3", "x1/x2/x4", "x1/x5")) {
        Tree<String> root = current;

        for (String data : tree.split("/")) {
            current = current.child(data);
        }

        current = root;
    }

    forest.accept(new PrintIndentedVisitor(0));

出力：

forest
  x1
    x2
      x3
      x4
    x5

他のヒント

各パスを区切り記号で分割し、ツリー構造に1つずつ追加します。
つまり、 'x1' が存在しない場合はこのノードを作成し、存在する場合はそこに進み、子 'x2' などがあるかどうかを確認します...

ツリーを一度に1つのストリングにします。

空のツリーを作成します（これにはルートノードがあります-＆quot; x7 / x8 / x9＆quot;のようなパスがある可能性があります）。

最初の文字列を取得し、x1をルートノードに追加し、x2をx1に追加し、x3をx2に追加します。

2番目の文字列を取得し、x1とx2が既に存在することを確認し、x4をx2に追加します。

すべてのパスに対してこれを実行します。

親（ノード）と子のリスト（ノード）を含むオブジェクトノードを作成します。

最初に＆quot;、＆quot;を使用して文字列を分割します。分割された文字列ごとに、＆quot; /＆quot;を使用して文字列を分割します。 ルートリストで最初のノード識別子（x1など）を検索します。 見つかったら、ノードを使用して次のノード識別子（x2など）を見つけます。

ノードが見つからない場合は、既存のリストで見つけられた最後のノードにノードを追加します。

リスト構造を作成した後、リストを画面に印刷できます。再帰的にします。

テストされていない、単なるアニメーション 

public void print(List nodes, int deep) {
    if (nodes == null || nodes.isEmpty()) {
        return;
    }

    StringBuffer buffer = new StringBuffer();
    for (int i = 0; i < deep; i++) {
        buffer.append("---");
    }

    for (Iterator iterator = nodes.iterator(); iterator.hasNext();) {
        Node node = (Node)iterator.next();

        System.out.println(buffer.toString() + " " + node.getIdentifier());

        print(node.getChildren(), deep + 1);
    }
}

配列内のすべての文字列に対してツリーを作成します。 '/'のパスを分割して、ノードがツリーに存在するかどうかを確認し、存在する場合は先に進みます...それ以外の場合は新しいノードを作成し、このノードを親ノードの子に追加します。

再帰を使用して繰り返します。

以下はツリーのノードのモデルです。

Class Node{
    string name;
    List<Node> childrens;

    Node(string name){
        this.name = name;
        this.childrens = new List<Node>();
    }
}
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top