Trie實現

Question

我正試圖在Java中實現一個非常簡單的Trie，它支持3個操作。我希望它有一個插入方法，一個has方法（也就是trie中的某個單詞）和一個toString方法以字符串形式返回trie。我相信我的插入工作正常，但已經和toString證明是困難的。這是迄今爲止我所擁有的。

trie類。

public class CaseInsensitiveTrie implements SimpleTrie { 

    //root node 
    private TrieNode r; 

    public CaseInsensitiveTrie() { 
     r = new TrieNode(); 
    } 

    public boolean has(String word) throws InvalidArgumentUosException { 
     return r.has(word); 
    } 

    public void insert(String word) throws InvalidArgumentUosException { 
     r.insert(word); 
    } 

    public String toString() { 
     return r.toString(); 
    } 

    public static void main(String[] args) { 

     CaseInsensitiveTrie t = new CaseInsensitiveTrie(); 

     System.out.println("Testing some strings"); 
     t.insert("TEST"); 
     t.insert("TATTER"); 
     System.out.println(t.has("TEST")); 
    } 
} 

和節點類

public class TrieNode { 

    //make child nodes 
    private TrieNode[] c; 
    //flag for end of word 
    private boolean flag = false; 

    public TrieNode() { 
     c = new TrieNode[26]; //1 for each letter in alphabet 
    } 

    protected void insert(String word) { 
     int val = word.charAt(0) - 64; 

     //if the value of the child node at val is null, make a new node 
       //there to represent the letter 
     if (c[val] == null) { 
      c[val] = new TrieNode(); 
     } 

     //if word length > 1, then word is not finished being added. 
     //otherwise, set the flag to true so we know a word ends there. 
     if (word.length() > 1) { 
      c[val].insert(word.substring(1)); 
     } else { 
      c[val].flag = true; 
     } 
    } 

    public boolean has(String word) { 
     int val = word.charAt(0) - 64; 
     if (c[val]!=null && word.length()>1) { 
      c[val].has(word.substring(1)); 
     } else if (c[val].flag==true && word.length()==1) { 
      return true; 
     } 

     return false; 
    } 

    public String toString() { 
     return ""; 
    } 
} 

因此，基本上，創造了特里的時候，一個TrieNode作爲與26名兒童的根目錄中創建。當試圖插入時，在該根節點上調用insert，遞歸地在正確的位置創建一個新節點，並繼續直到該單詞完成。我相信該方法正常工作。

我的功能非常壞，因爲我有由於某種原因在括號外有return語句。我不能在一個else子句中包含它，或者編譯器抱怨。除此之外，我認爲這種方法應該可以進行一些調整，但我無法想象出我的生活。 toString是我試圖解決的一個野獸，但沒有任何我扔在它的作品，所以我會離開那個，直到我解決了問題。如果我有工作，我可能會想辦法將其重新格式化爲toString函數。

int val = word.charAt（0） - 64;是因爲輸入的每個字符串必須全部大寫（我將創建一個字符串格式化函數以確保此後），因此第一個字母的int值 - 64將是它在數組中的位置。即數組索引0是A，所以A = 64，A-64 = 0。B = 65，B-64 = 1等等。

Answer 1

你has功能大概應該是這樣的：

if (c[val]!=null && word.length()>1) { 
    return c[val].has(word.substring(1)); //<-- Change is on this line 
} else if (c[val].flag==true && word.length()==1) { 
    ...etc 

您進行遞歸調用，但你真的需要讓該值傳播回了原來的調用者。

Answer 2

也許你可以使用「地圖C」而不是「TrieNode [] C」，這將允許你使用這種字符的所有類型的大寫/小寫甚至特殊字符，甚至會節省你的空間（分配在每個人物等級26字符數組）

Answer 3

This Trie Map實現has (called get in this implementation)和toString

Answer 4

這裏是我的實現： -

public class Tries { 

class Node { 
    HashMap<Character, Node> children; 
    boolean end; 
    public Node(boolean b){ 
     children = new HashMap<Character, Tries.Node>(); 
     end = false; 
    } 
} 
private Node root; 
public Tries(){ 
    root = new Node(false); 
} 
public static void main(String args[]){ 
    Tries tr = new Tries(); 
    tr.add("dog"); 
    tr.add("doggy"); 

    System.out.println(tr.search("dogg")); 
    System.out.println(tr.search("doggy")); 
} 
private boolean search(String word) { 
    Node crawl = root; 
    int n = word.length(); 
    for(int i=0;i<n;i++){ 
     char ch = word.charAt(i); 
     if(crawl.children.get(ch) == null){ 
      return false; 
     } 
     else { 
      crawl = crawl.children.get(ch); 
      if(i==n-1 && crawl.end == true){ 
       return true; 
      } 

     } 
    } 
    return false; 
} 
private void add(String word) { 
    Node crawl = root; 
    int n = word.length(); 
    for(int i=0;i<n;i++){ 
     char ch = word.charAt(i); 
     if(crawl.children.containsKey(ch)){ 
      crawl = crawl.children.get(ch); 
     } 
     else { 
      crawl.children.put(ch, new Node(false)); 
      Node temp = crawl.children.get(ch); 
      if(i == n-1){ 
       temp.end = true; 
      } 
      crawl = temp; 
      System.out.println(ch + "  " + crawl.end); 

     } 
    } 
} 

} 

Answer 5

這裏是無u簡單的Java實現唱任何其他數據結構

import java.util.ArrayList; 
import java.util.List; 

class Trie { 

    private static Node root = new Node(' ', false); 

    static int getIndex(char x) { 
     return ((int) x) - ((int) 'a'); 
    } 

    static class Node { 
     char data; 
     boolean isLeaf; 
     Node[] children; 

     Node(char data, boolean leaf) { 
      this.data = data; 
      this.isLeaf = leaf; 
      this.children = new Node[26]; 
     } 

    } 

    static void insert(String data, Node root) { 
     if (data == null || data.length() == 0) { 
      return; 
     } 
     Node child = root.children[getIndex(data.charAt(0))]; 
     if (child == null) { 
      Node node = new Node(data.charAt(0), data.length() == 1); 
      root.children[getIndex(data.charAt(0))] = node; 
      if (data.length() > 1) { 
       insert(data.substring(1, data.length()), node); 
      } 
     } else { 
      if (data.length() == 1) { 
       child.isLeaf = true; 
      } else { 
       insert(data.substring(1, data.length()), child); 
      } 
     } 
    } 

    static boolean find(String data, Node root) { 
     if (data == null || data.length() == 0) { 
      return true; 
     } 
     char x = data.charAt(0); 
     //note that first node ie root is just dummy, it just holds important 
     Node node = root.children[getIndex(x)]; 
     if (node == null) { 
      return false; 
     } else { 
      if (data.length() == 1) { 
       return node.isLeaf; 
      } else { 
       return find(data.substring(1, data.length()), node); 
      } 
     } 
    } 

    static boolean delete(String data, Node root) { 
     if (data == null || data.length() == 0) { 
      return false; 
     } 
     char x = data.charAt(0); 
     //note that first node ie root is just dummy, it just holds important 
     Node node = root.children[getIndex(x)]; 
     if (node == null) { 
      return false; 
     } else { 
      if (data.length() == 1) { 
       node.isLeaf = false; 
       boolean allNull = true; 
       for (Node node1 : node.children) { 
        allNull = allNull && node1 == null; 
       } 
       return allNull; 
      } else { 
       boolean delete = delete(data.substring(1, data.length()), node); 
       if (delete) { 
        node.children[getIndex(x)] = null; 
        if(node.isLeaf){ 
         return false; 
        } 
        boolean allNull = true; 
        for (Node node1 : node.children) { 
         allNull = allNull && node1 == null; 
        } 
        return allNull;    } 
      } 
     } 
     return false; 
    } 


    private static List<String> strings = new ArrayList<>(); 

    private static List<String> getAll() { 
     strings = new ArrayList<String>(); 
     findAllDFS(root, ""); 
     return strings; 
    } 

    private static void findAllDFS(Node node, String old) { 
     if (node != null) { 
      if (node.data != ' ') { 
       old = old + node.data; 
      } 
      if (node.isLeaf) { 
       strings.add(old); 
      } 
      for (Node node1 : node.children) { 
       findAllDFS(node1, old); 
      } 
     } 
    } 

    public static void main(String[] args) { 
     insert("abc", root); 
     insert("xyz", root); 
     insert("abcd", root); 
     insert("abcde", root); 


     delete("abcd", root); 

/*  System.out.println(find("abc", root)); 
     System.out.println(find("abcd", root)); 
     System.out.println(find("ab", root)); 
     System.out.println(find("xyz", root));*/ 


     System.out.println(getAll()); 
    } 


} 

Answer 6

這裏我實現的：

public class Tries { 
private static class Leaf { 
    private Leaf(char c) { 
     this.c=c; 
    } 
    char c; 
    int counter = 1; 
    List<Leaf> leaves = new ArrayList<>(10); 
} 
private Leaf root = new Leaf('0'); 
public void add(String word) { 
    Leaf current = root; 
    Leaf newLeaf = null; 
    for (char c : word.toCharArray()) { 
     boolean found = false; 
     for (Leaf leaf : current.leaves) { 
      if (leaf.c == c) { 
       current = leaf; 
       current.counter++; 
       found=true; 
       break; 
      } 
     } 
     if (!found) { 
      newLeaf = new Leaf(c); 
      current.leaves.add(newLeaf); 
      current = newLeaf; 
     } 
    } 
} 
public int find(String partial) { 
    Leaf current = root; 
    for (char c : partial.toCharArray()) { 
     boolean found = false; 
     for (Leaf leaf : current.leaves) { 
      if (leaf.c == c) { 
       current=leaf; 
       found=true; 
       break; 
      } 
     } 
     if(!found) return 0; 
    } 
    return current.counter; 
} 

public boolean hasWord(String partial) { 
    return find(partial)>0; 
    } 
}