Tree. A tree stores nodes. Each node can reference other nodes—these are child nodes. In Java we can develop a simple tree to store many strings.
With this method, we store a HashMap on each node. This map points to child nodes. To traverse the tree, we access elements in the HashMap.
Example program. This program is simple. We first see the TreeNode class—this contains the children node (in a HashMap). We also have get and add() methods.
Start In the Program class we have an addWord and an exists() method. These handle strings and manipulate the tree.
Next AddWord() loops over all the characters in the String. It calls add() on each letter to add nodes.
Finally Exists() tests the tree to see if a string exists in it. The result is a boolean.
import java.util.HashMap;
class TreeNode {
boolean word;
HashMap<Character, TreeNode> children = new HashMap<>();
public TreeNode get(char value) {
// Get anode from the HashMap.
return children.getOrDefault(value, null);
}
public TreeNode add(char value, TreeNode node) {
// Add a node if one does not yet exists.// ... Return the matching node.
children.putIfAbsent(value, node);
return get(value);
}
}
public class Program {
static TreeNode root = new TreeNode();
static void addWord(String value) {
// Add all characters from the string to the tree.
TreeNode node = root;
for (int i = 0; i < value.length(); i++) {
node = node.add(value.charAt(i), node);
}
node.word = true;
}
static boolean exists(String value) {
// See if a word exists in the tree.
TreeNode node = root;
for (int i = 0; i < value.length(); i++) {
node = node.get(value.charAt(i));
if (node == null) {
return false;
}
}
return node.word;
}
public static void main(String[] args) {
// Add three words to the tree.
addWord("cat");
addWord("bird");
addWord("dog");
// These three words should exist.
boolean exists1 = exists("cat");
boolean exists2 = exists("bird");
boolean exists3 = exists("dog");
System.out.println(exists1);
System.out.println(exists2);
System.out.println(exists3);
// These words do not exist.
exists1 = exists("fish");
exists2 = exists("123456");
exists3 = exists("turnip");
System.out.println(exists1);
System.out.println(exists2);
System.out.println(exists3);
}
}true
true
true
false
false
false
Tests. In the main() method we test the tree with the addWord and exists() methods. We add three strings—exists returns true on these strings.
And The exists() method fortunately returns false on the strings we did not add to the tree.
Some performance issues. A tree like this one can be used to optimize string lookups. This can implement a Scrabble or anagram program.
However The implementation here is not perfect. The HashMap could be changed to an array of TreeNode references.
And With an array, we could lazily allocate the array to save memory. We could use a lookup method to match chars to indexes.
A review. Trees (tries) are powerful. In the field of artificial intelligence, nodes represent search steps. And traversing a tree is a performance challenge.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on May 20, 2023 (simplify).