Below is the code. The array index represents the small characters(a-z) and index is 26 (number of characters in english alphabets). It is a dictionary of words in which the children[character ascii value-97] points to the next node. The end of word is given bool terminal=true.
All functions are recursive. In delete function, we have to traverse to the end of the word character by character. While traversing, on the second call of recursive delete, I lose all my references and NullPointerException occurs.
The line of code which is making trouble has a comment in front of it. First there is a check if word exist in dictionary or not.
import java.io.File;
import java.util.Scanner;
public class xxx {
public static void main(String[] args) {
Trie trie = new Trie();
if (trie.delete(word)) {
System.out.println("Word deleted");
} else {
System.out.println("Word not present");
}
break;
}
case "S": { //Search for the word
String word = tokens[1];
if (trie.isPresent(word)) {
System.out.println("Word found");
} else {
System.out.println("Word not found");
}
}
This class just calls the recursive functions of the Node class. The trie class gets call from the main class and then shifts the data to recursive functions in Node class
class Trie {
Node root;
public Trie() {
root = new Node();
}
boolean isPresent(String s) { // returns true if s is present, false otherwise
current = root;
for (int i = 0; i < s.length(); i++) {
if (current.children[(int) s.charAt(i) - 97] == null) {
return false;
} else {
current = current.children[(int) s.charAt(i) - 97];
}
}
if (current.terminal == false) {
return false;
}
return true;
}
boolean delete(String s) { // returns false if s is not present, true otherwise
if (!isPresent(s)) {
return false;
}
root.delete(root,s);
return true;
}
int membership() { // returns the number of words in the data structure
return root.membership(root, 0);
}
void listAll() { // list all members of the Trie in alphabetical orber
root.listAll(root, "");
}
}
The children[ascii value-97] will reference a node and this link will represent alphabetic character. The outDegree will make sure that only the given string is deleted. This class has all recursive functions.
class Node {
boolean terminal;
int outDegree;
Node[] children;
public Node() {
terminal = false;
outDegree = 0;
children = new Node[26];
}
public void delete(Node x, String s) {
if (s.length() > 1){
if(i<s.length())
delete(children[s.charAt(0)-97],s.substring(1)); //this is where problem occurs
}
else if(children[((int)s.charAt(0))-97].outDegree>0)
terminal =false;
else if(children[((int)s.charAt(0))-97].outDegree==0){
children[((int)s.charAt(0))-97]=null;
return;
}
if(children[s.charAt(0)-97].outDegree==0)
children[s.charAt(0)-97]=null;
}
}
