Trie/Tree addWord() method

[nisaa15]

Hi All,

Im trying to implement a trie in java(which is basically a tree used to store words). I have the following method to add a word but am unsure how i would go about check to see if the prefix of a word already exists. Heres my code:

public void add(String word){
for (int i = 0; i<=word.length(); i++){
char c = word.charAt(i);
if(c==..............(trieEdge(c))){  //unsure about this, should check whether an edge with the character c exists in the ith position.
i++;//should go to the next character and node if an edge exists
}  else{
word.makeEdge(c);
}

//hereafter I check to see if the end of the word has been reached in wich case the makeNode/edge would place a terminal node at the end rather than a normal node.

If anyone can give me suggestions as to how I can check to see if the edge already exists in correspondance to the ith position this will be very much appreciated

Cheers

[server_crash]

startsWith(String prefix)
endsWith(String postfix)

[nisaa15]

how would i know which node im talking about, i want to do it so that the program checks individual characters rather than prefixes. so i would have to check a nodes children but how can i determine which node the program should look at. It should start by looking at the rott nodes children and if the edge exists here follow the edge to the next node and check to see if the next character is amonst the new nodes children and so forth.

[server_crash]

What do you mean you don't know what node to look at?

[nisaa15]

What do you mean you don't know what node to look at?

Well I want to start the search from the root node. How can I represent the edges that the node has? once the computer knows if the edge exists if will follow this edge through to it destination node. My problem is - how do I represent the edges one node has?

[Daishi]

Well I want to start the search from the root node. How can I represent the edges that the node has? once the computer knows if the edge exists if will follow this edge through to it destination node. My problem is - how do I represent the edges one node has?

Well, if you are using Java, this is pretty darn easy to do. Each node could have a list of node references (or pointers, in other languages) within its structure. For example:

class Node {
    //  Note that this is public for example only, you should write your own setting and accessing methods for the nodes.
    public Node childOne, childTwo;

    public Node() {
        childOne=null;
        childTwo=null;
    }
}

This example class could be a node in a tree. Note that childOne and childTwo are just references to Node objects, and are set to null in the constructor. childOne and childTwo can represent the children of that particular node. Each node will actually represet a sub tree using this method. So, you can just do this in your tree structure:

class Tree {
    public Node root;
}

Of course, you can have more than just two node references in your node class. You could just have one node (which would be a linked list), or you could even have a list of nodes (which would be a full blown tree). For your example you probably want each node to have two child nodes, and create a binary search tree from that. Google would be a good place to start for finding out more.

-Fredric