fork(2) download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class TST {
  6.  
  7. private Node root;
  8.  
  9. public void put(String key, int value) {
  10.     root = put(root, key, value, 0);
  11. }
  12.  
  13.  
  14. private Node put(Node node, String key, int value, int index) {
  15.  
  16.     char c = key.charAt(index);
  17.  
  18.     if( node == null ){
  19.         node = new Node(c);
  20.     }
  21.  
  22.     if( c < node.character ){
  23.         node.left = put(node.left,key,value,index);
  24.     }else if( c > node.character ){
  25.         node.right = put(node.right,key,value,index);
  26.     }else if( index < key.length()-1 ){
  27.         node.middle = put(node.middle,key,value,index+1);
  28.     }else{
  29.         node.value = value;
  30.     }
  31.  
  32.     return node;
  33. }
  34.  
  35. public Integer get(String key) {
  36.     Node node = get(root, key, 0);
  37.  
  38.     if (node == null) {
  39.         return null;
  40.     }
  41.  
  42.     return node.value;
  43.  
  44. }
  45.  
  46. public Node get(Node node, String key, int index) {
  47.     if(node == null) {
  48.         return null;
  49.     }
  50.  
  51.     char c = key.charAt(index);
  52.  
  53.     if (c < node.character) {
  54.         return get(node.left, key, index);
  55.     } else if (c > node.character) {
  56.         return get(node.right, key, index);
  57.     } else if(index < key.length() -1) {
  58.         return get(node.middle, key, index);
  59.     } else {
  60.         return node;
  61.     }
  62.  
  63. }
  64.  
  65. public void inorderTraversal(Node node, String word) {
  66.     if (node.value != 0) {
  67.         System.out.println(word + node.character + ": " + node.value);
  68.     }
  69.  
  70.     if(node.left != null) {
  71.         inorderTraversal(node.left, word);
  72.     }
  73.  
  74.     if (node.middle != null) {
  75.         inorderTraversal(node.middle, word + node.character);
  76.     }
  77.  
  78.     if(node.right != null) {
  79.         inorderTraversal(node.right, word);
  80.     }
  81. }
  82.  
  83. public void traverse() {
  84.     inorderTraversal(root, "");
  85. }
  86.  
  87. }
  88.  
  89. public class Main {
  90.  
  91. public static void main(String[] args) {
  92.     TST tst = new TST();
  93.     tst.put("This",3);
  94.     tst.put("There",4);
  95.     tst.put("Them",5);
  96.     tst.put("High",6);
  97.     tst.put("The",7);
  98.     tst.traverse();
  99.  
  100. }
  101.  
  102. }
  103.  
  104. class Node {
  105.  
  106. public char character;
  107. public Node left, right, middle;
  108. public int value;
  109.  
  110. public Node(char character) {
  111.     this.character = character;
  112. }
  113. }
Success #stdin #stdout 0.09s 27756KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
High: 6
The: 7
Them: 5
There: 4
This: 3
https://ideone.com/WqxHX5
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!