java - Questions about recusive methods for generating a tree -

java - Questions about recusive methods for generating a tree -

i trying understand simple spell checker program. programme read dictionary file, set words in tree. when performs check function, takes word @ time file checking, , see if word in tree, using retrieve().

my question don't understand how "add" method works. supposed add together words dictionary tree structure. please help me explain how works? many thanks!

private static binarysearchtree<stringitem, string> tree = new binarysearchtree<stringitem, string>(); //does create tree stringitems nodes? //in part method assign value tree nodes? private static arraylist<string> dictionary;//number number of strings in dictionary private static treenode<stringitem> add together (int number) { // adds tree //the numberofwords has been counted in other methods. if (numberofwords < 1) { homecoming null; } treenode<stringitem> left = add(number / 2); //what do? stringitem word = new stringitem(dictionary.remove(0) + ""); treenode<stringitem> right = add((number - 1) / 2); homecoming new treenode<stringitem>(word, left, right); // don't understand part. //which node returning here? }

check out this really implementation of binary search tree written folks @ princeton (as matter of fact - check out really implementations they've published sorts of fundamental algorithms here)

i'm little unclear specific question is, lets start this:

private static binarysearchtree<stringitem, string> tree = ... //does create tree string items nodes?

i think help if think of bst beingness more map (with keys of 1 type mapped values of type) rather simple list of objects of single type. if @ implementation linked above, think bit clearer:

public class bst<key extends comparable<key>, value> { private class node { private key key; // sorted key private value val; // associated info private node left, right; // left , right subtrees private int n; // number of nodes in subtree ... } ... private node put(node x, key key, value val) { if (x == null) homecoming new node(key, val, 1); int cmp = key.compareto(x.key); if (cmp < 0) x.left = put(x.left, key, val); else if (cmp > 0) x.right = put(x.right, key, val); else x.val = val; x.n = 1 + size(x.left) + size(x.right); homecoming x; } ... }

note type parameters explicitly named key , value here, should reinforce saying above. note node contains both key and value - value "payload", actual info beingness being stored, while key used sorting , organizing tree (hence key must implement comparable). aside, note instead of add(), equivalent method here called put(), think clearer because we're accustomed calling put(k, v) on map-like structures , add(t) on lists (i'm wondering whether might have played role in confusion)

like said though, i'm not exclusively sure you're confused about. i've said i've said here because seems you're asking type parameters, you're unclear on else post comment , i'll update.

(that said, included entire method above because, if you're trying understand how bsts function in general, that's of import method understand. go through , figure out each line doing , why its's beingness done way. same get(), , you'll on way).

java recursion data-structures arraylist tree