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.a具有两个节点的路径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 回答
1

这是一个Java版本（未经测试）。请注意，这是完整的。它不需要对输入字符串进行任何初始转换。它还保留了树节点的插入顺序：

public class Node implements Iterable<Node> {
    private String name;
    private Map<String, Node> children = new LinkedHashMap<String, Node>();

    public Node(String name) {
        this.name = name;
    }

    public String getName() { return this.name; }

    public Iterator<Node> iterator() { return children.values().iterator(); }

    private Node lookupOrAddChild(String name) {
        Node child = children.get(name);
        if (child = null) {
            child = new Node(name);
            children.put(name, child);
        }
        return child;
    }

    private void addLine(String line) {
        int pos = line.indexOf(".");
        if (pos < 0) {
            lookupOrAddChild(line);
        } else {
            node = lookupOrAddChild(line.subString(0, pos));
            node.addLine(line.substring(pos + 1));
        }
    }

    public static Node buildTree(String[] input) {
        Node node = new Node("");
        for (String line : input) {
           node.addLine(line);
        }
        // This assumes the input forms exactly one "tree"
        return node.children.values().iterator().next();
    }
于 2013-05-09T14:07:56.437 回答
1

这可以使用Trie 数据结构轻松解决

以下是使用 Java 实现 Trie 数据结构 

import java.util.*;
class Tree
{
    class Node
    {
        String data;
        ArrayList<Node> children;

        public Node(String data)
        {
            this.data = data;
            children = new ArrayList<Node>();
        }

        public Node getChild(String data)
        {
            for(Node n : children)
                if(n.data.equals(data))
                    return n;

            return null;
        }
    }

    private Node root;

    public Tree()
    {
        root = new Node("");
    }

    public boolean isEmpty()
    {
        return root==null;
    }

    public void add(String str)
    {
        Node current = root;
        StringTokenizer s = new StringTokenizer(str, ".");
        while(s.hasMoreElements())
        {
            str = (String)s.nextElement();
            Node child = current.getChild(str);
            if(child==null)
            {
                current.children.add(new Node(str));
                child = current.getChild(str);
            }
            current = child;
        }
    }

    public void print()
    {
        print(this.root);
    }

    private void print(Node n)
    {
        if(n==null)
            return;
        for(Node c : n.children)
        {
            System.out.print(c.data + " ");
            print(c);
        }
    }
}

要验证实现，请使用以下类 

import java.io.*;
public class TestTree
{
    public static void main(String[] args) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Tree t = new Tree();
        String s;
        int i=7;
        while(i-->0)
        {
            s = br.readLine();
            t.add(s);
        }
        System.out.println("Tree constructed!");
        t.print();
    }
}

add 算法 方法
1. 它以字符串作为输入。
2. 它在句点 (.) 处拆分字符串
3. 对于获得的每个子字符串（拆分后），检查值，如果该字符串已经存在于树中，则它遵循该路径，否则它将插入一个新字符串（新节点）在当前级别

该代码适用于输入 

a.b.c.d
b.c.d.e
a.e.f.a
c.d.f.c
etc

这意味着第一级可以有任何字符串

注意：
在我i=7为测试目的设置的 TestTree.java 中，
您可以提供 7 个输入测试用例 

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

Print 方法使用前序遍历打印 Tree 的数据。它仅用于验证目的，您可以根据需要对其进行调整。

希望这可以帮助！:)

于 2013-05-10T05:23:23.883 回答
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 回答