3

次のような内容のテキスト ファイルがあります。

a.b.c.d
a.c
a.d
a.x.y.z
a.x.y.a
a.x.y.b
a.subtree

これをツリーにしたい：

                        a
                  /  /    \  \   \
                 b   c     d   x  subtree
                 |              |
                 c              y   
                 |            / | \
                 d            z a  b

編集: a.x.y.a2 つのノードを含むパスは、a別個のエンティティとして扱う必要があります。基本的にa.x.y.aはパスです。

入力ファイルは次のように表示できます。

Level0.Level1.Level2...

私はPythonでこれをやろうとしています（私もJavaに精通していて、Javaの回答も欲しいです）が、どういうわけか私は論理的にそれを行うことができません.

私の基本的なツリー構造は次のようなものです。

 class Tree:
     def __init__(self,data):
         self.x = data
         self.children = []

ロジックは次のようになります。

for line in open("file","r"):
    foos = line.split(".")
    for foo in foos:
        put_foo_in_tree_where_it_belongs()

これにどのように正確にアプローチしますか？

また、これを行うのに役立つJavaライブラリがあれば、 Java に移行することもできます。これを達成するだけです。

4

5 に答える 5

3

基本的なアルゴリズムは次のようになります。

def add_path(root, path):
    if path:
        child = root.setdefault(path[0], {})
        add_path(child, path[1:])

root = {}
with open('tree.txt') as f:
    for p in f:
        add_path(root, p.strip().split('.'))

import json
print json.dumps(root,  indent=4)

出力：

{
    "a": {
        "x": {
            "y": {
                "a": {}, 
                "z": {}, 
                "b": {}
            }
        }, 
        "c": {}, 
        "b": {
            "c": {
                "d": {}
            }
        }, 
        "d": {}, 
        "subtree": {}
    }
}
于 2013-05-09T13:00:53.213 に答える
2

私はこれを行うと思います：

class Node(object):
    def __init__(self,data=None):
        self.children = []
        self.data = data

    def add_from_dot_str(self,s):
        elems = s.split('.')
        if self.data is None:
            self.data = elems[0]
        elif self.data != elems[0]:
            raise ValueError
        current = self
        for elem in elems[1:]:
            n = Node(elem)
            current.children.append(n)
            current = n

    @classmethod
    def from_dot_file(cls,fname):
        with open(fname) as fin:
            root = Node()
            for line in fin:
                root.add_from_dot_str(line.strip())

        return root

    def __str__(self):
        s = self.data
        s += ','.join(str(child) for child in self.children)
        return s

print Node.from_dot_file('myfilename')
于 2013-05-09T12:47:23.473 に答える
0

「Javaの回答も欲しい」という理由だけで、Javaソリューションを提供しました:)使用するには、入力を解析し、それらをキューにプッシュしてinsertFromRoot(Queue)を呼び出します

public class CustomTree {

    private TreeNode root;

    public class TreeNode {
        String                value;
        Map<String, TreeNode> children = new HashMap<String, TreeNode>();

        public TreeNode(String val) {
            this.value = val;
        }
    }

    public void insertFromRoot(Queue<String> strings) {
        if (strings != null && !strings.isEmpty()) {
            if (root == null) {
                root = new TreeNode(strings.poll());
            } else {
                if (!root.value.equals(strings.poll())) {
                    throw new InvalidParameterException("The input doesnt belong to the same tree as the root elements are not the same!");
                }
            }
        }

        TreeNode current = root;
        while (!strings.isEmpty()) {
            TreeNode newNode = null;
            if (current.children.containsKey(strings.peek())) {
                newNode = current.children.get(strings.poll());
            } else {
                newNode = new TreeNode(strings.poll());
                current.children.put(newNode.value, newNode);
            }
            current = newNode;
        }

    }
}

編集：

簡単な使い方:

public static void main(String[] args) {
        Queue<String> que = new LinkedList<String>();
        que.add("a");
        que.add("b");
        que.add("c");

        Queue<String> que2 = new LinkedList<String>();
        que2.add("a");
        que2.add("b");
        que2.add("d");

        CustomTree tree = new CustomTree();
        tree.insertFromRoot(que);
        tree.insertFromRoot(que2);
    }
于 2013-05-09T13:58:34.073 に答える