我該如何創建一棵樹？

Question

我有有這樣內容的文本文件：

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節點的a.x.y.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。只需要做到這一點。

Answer 1

的基本算法應該是這樣的：

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": {} 
    } 
} 

Answer 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') 

Answer 3

只是爲了「想Java的答案以及「，我提供了一個Java解決方案:) 使用，解析你的輸入，推入一個隊列中的呼叫insertFromRoot（隊列）

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); 
    } 

Answer 4

下面是一個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(); 
    } 

Answer 5

這可以使用Trie Data Structure

繼迎刃而解是特里數據結構使用Java

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(); 
    } 
} 

加法算法
1.將字符串作爲輸入。
2.以句點（。）分割字符串
3.對於獲得的每個子字符串（分割後），檢查該值，如果該字符串已經存在於樹中，那麼它遵循該路徑，否則它將插入新的字符串（新節點）在當前水平

代碼將進行輸入工作良好

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

這意味着第一級可以有任何字符串

注：
在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 

打印方法打印使用序遍歷的樹的數據集i=7。這只是爲了驗證目的，你可以根據你的需要調整它。

希望這會有所幫助！ :)