Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Learning Binary Trees through recursive programming.
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
/*
* Sample application output:
*
* **** Building Dictionary Start with Isabella ****
*
* **** Populate Dictionary *****
*
* Inserted Ethan to left of Isabella
* Inserted Mia to right of Isabella
* ..........
*
* **** Print Dictionary ****
*
* Traversed Ethan
* Traversed Isabella
* Traversed Mia
*
* **** Number of words in dictionary: 3
*
* **** Reversed Dictionary Input ****
* Mia, Isabella, Ethan
*/
public class Dictionary
{
public static void main(String[] args)
{
String nameString = new String("Jacob, Sophia, Michael, Olivia, William, Emily, Noah, Madison, Aiden, Chloe, Anthony");
String[] namesArray = nameString.split(", ");
Dictionary dictionary = new Dictionary();
Node rootNode = dictionary.buildDictionary(namesArray);
System.out.print("\n");
System.out.println("**** Print Dictionary ****\n");
dictionary.printDictionary(rootNode);
System.out.print("\n");
int wordCount = 0;
wordCount = dictionary.dictionaryWords(rootNode, wordCount);
System.out.print("**** Number of words in dictionary: " + wordCount + "\n");
System.out.print("\n");
System.out.println("**** Reversed Dictionary Input ****");
String nameStringReversed = dictionary.reverseDictionaryInput(namesArray);
System.out.print(nameStringReversed + "\n\n");
}
public Node buildDictionary(String[] namesArray)
{
// This is a method which call the method populateDictionary method
// which populate your binary tree
Node rootNode = new Node(namesArray[0]);
System.out.println("**** Building Dictionary Start with " + rootNode.value + " ****\n");
System.out.println("**** Populate Dictionary *****\n");
for (String name : namesArray) {
populateDictionary(rootNode, name);
}
return rootNode;
}
public int dictionaryWords(Node n, int wc)
{
// This is a method which traverses over the tree and count the
// number of the node in the tree.
if (n != null) {
wc++;
wc = dictionaryWords(n.left, wc);
wc = dictionaryWords(n.right, wc);
}
return wc;
}
public void populateDictionary(Node n, String v)
{
// This method will populate your binary tree
if (v.compareTo(n.value) < 0) {
if (n.left != null) {
populateDictionary(n.left, v);
} else {
System.out.println(" Inserted " + v + " to left of " + n.value);
n.left = new Node(v);
}
} else if (v.compareTo(n.value) > 0) {
if (n.right != null) {
populateDictionary(n.right, v);
} else {
System.out.println(" Inserted " + v + " to right of " + n.value);
n.right = new Node(v);
}
}
}
public void printDictionary(Node n)
{
// This is a method which traverse over the tree and print each
// ascending sorted node alphabetically
if (n != null) {
printDictionary(n.left);
System.out.println(" Traversed " + n.value);
printDictionary(n.right);
}
}
public String reverseDictionaryInput(String[] namesArray)
{
// This is a method which take the original input and reverse it using
// appropriate java data structure
// String reverse = "Albert, Suzan, Peggy "
List<String> namesList = Arrays.asList(namesArray);
Collections.sort(namesList, String.CASE_INSENSITIVE_ORDER);
Collections.reverse(namesList);
StringBuilder namesReversed = new StringBuilder();
for (String name : namesList) {
namesReversed.append(name + ", ");
}
return namesReversed.delete(namesReversed.length() - 2, namesReversed.length()).toString();
}
private static class Node
{
Node left;
Node right;
String value;
public Node(String v)
{
value = v;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.