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