How do I print all the words out in a Trie?
972 观看
1回复
I have a Ternary Search Tree (Trie) and I want to print out all of the words in it.
How do I go about this using this current implementation that I have below?
I have a standard put
method to add new words to the tree. I was attempting to print the words using an in-order traversal, but I'm unsure how exactly to complete the function.
class TST {
private Node root;
public void put(String key, int value) {
root = put(root, key, value, 0);
}
private Node put(Node node, String key, int value, int index) {
char c = key.charAt(index);
if( node == null ){
node = new Node(c);
}
if( c < node.character ){
node.left = put(node.left, key, value, index);
}else if( c > node.character ){
node.right = put(node.right, key, value, index);
}else if( index < key.length()-1 ){
node.middle = put(node.middle, key, value, index+1);
}else{
node.value = value;
}
return node;
}
public Integer get(String key) {
Node node = get(root, key, 0);
if (node == null) {
return null;
}
return node.value;
}
public Node get(Node node, String key, int index) {
if(node == null) {
return null;
}
char c = key.charAt(index);
if (c < node.character) {
return get(node.left, key, index);
} else if (c > node.character) {
return get(node.right, key, index);
} else if(index < key.length() -1) {
return get(node.middle, key, index);
} else {
return node;
}
}
public void inorderTraversal(Node node) {
System.out.print(node.character + ":" + node.value + " ");
if(node.left != null) {
inorderTraversal(node.left);
}
if(node.middle != null) {
inorderTraversal(node.middle);
}
if(node.right != null) {
inorderTraversal(node.right);
}
}
public void traverse() {
inorderTraversal(root);
}
}
public class Main {
public static void main(String[] args) {
TST tst = new TST();
tst.put("This",3);
tst.put("There",4);
tst.put("Them",5);
tst.put("High",6);
System.out.println(tst.get("T"));
tst.traverse();
}
}
class Node {
public char character;
public Node left, right, middle;
public int value;
public Node(char character) {
this.character = character;
}
}
的来源
发布者: 2019 年 11 月 21 日
回应 (1)
0像
Since each node only stores a single character, you need to pass along a String (or StringBuilder, if you're trying to be efficient) representing the prefix defined by the path from the root when doing your traversal.
As per the definition of a ternary search tree, you should only append to this prefix when going to the middle node.
An example implementation:
public void inorderTraversal(Node node, String word) {
// handle end of word
if (node.value != 0) {
System.out.println(word + node.character + ": " + node.value);
}
if(node.left != null) {
inorderTraversal(node.left, word);
}
if (node.middle != null) {
inorderTraversal(node.middle, word + node.character);
}
if(node.right != null) {
inorderTraversal(node.right, word);
}
}
public void traverse() {
inorderTraversal(root, "");
}
Demo.
It's also possible to store the String representing the full word at each node during construction, since you already have the complete word in your put
method (if you're not worried about the memory usage).
Note that this / your code doesn't allow for mapping words to a 0 value - one way to deal with that is to use Integer
instead of int
, then you can use != null
to check for the end of a word.
来自类别的问题 :
- java Java和C#中的int和Integer有什么区别?
- java 如何在Java中确定路由器/网关的IP?
- java 根据XSD文件验证XML文件的最佳方法是什么?
- java 如何整理整数除法的结果?
- java 将List <Integer>转换为List <String>
- algorithm Function for creating color wheels
- algorithm 大O,你如何计算/近似它?
- algorithm 测量信号的峰值检测
- algorithm 拼图:找到最大的矩形(最大矩形问题)
- algorithm 合并排序链接列表
- data-structures C#中的树数据结构
- data-structures 如何按字典值对字典列表进行排序?
- data-structures 如何从Java中删除数组中的对象?
- data-structures 您将如何在Java中实现LRU缓存?
- data-structures 跳过列表 - 曾经使用过吗?
- ternary-search-tree How do I print all the words out in a Trie?