Trie is a very simple data structure. I coded it back in java as a
component of the software. If you want the code then here it is:
class Node{
boolean isFinal;
Node[] link;
int id;
Node parent;
int group;
static int numNodes = 0;
boolean hasChild;
public Node(){
isFinal = false;
id = numNodes++;
link = new Node[27];
hasChild = false;
}
}
public class Trie{
Node start;
int totalNodes;
Node insert(Node root, String[] labels, int n){
if (root == null){
totalNodes++;
root = new Node();
}
if (labels.length == n) {
root.isFinal = true;
}
else {
if(labels[n].charAt(0) == '-'){
root.link[26] = insert(root.link[26], labels,
n+1);
root.link[26].parent = root;
}
else{
root.link[labels[n].charAt(0) - 'A'] =
insert(root.link[labels[n].charAt(0) - 'A'], labels, n+1);
root.link[labels[n].charAt(0) - 'A'].parent =
root;
}
root.hasChild = true;
}
return root;
}
void build(String fileName) throws IOException{
BufferedReader reader = new BufferedReader(
new InputStreamReader(new DataInputStream(
new FileInputStream(fileName))));
String line = null;
while((line = reader.readLine()) != null){
line = line.trim();
if(!line.equals("")){
String[] labels = line.split("\\s+");
start = insert(start, labels, 0);
}
}
}
}
On Jun 23, 11:24 am, Raj N <[email protected]> wrote:
> Hi,
> Can anyone explain me the implementation of trie. I would be grateful
> if one could provide me the link to a good learning resource.
> Thanks!!
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
