Go to the Node class and finish the Node data structure: (JAVA)

The Node class is used to build ternary trees. A ternary tree is very similar to a binary tree, except that it can have up to 3 children: left, center, and right.

Then finish the two methods in the PQ4 class

buildTree

static void buildTree(char[] letters)

Add letters to ternary tree using a level-order traversal (breadth first search).

Take a moment to look over the setup code and implement the while loop.

Remove a node, curr, from the Queue and assign it into a temporary variable

Assign the next three letters to curr's left, center, and right children.

Add the children into the queue in the same order as above.

You can assume that char[] letters will always contain i * 3 + 1 letters.

Parameters:

letters - an array of letters

printTree

static void printTree(Node current, java.lang.String answer)

Traverse the tree using recursion and print the letters contained in every path from the root to a leaf node.

Follow this algorithm:

If the node specified is null, return immediately. This is a base case.

Add the letter contained in the current node to the answer string.

Check whether the node is a leaf node (if all children references are null).

If all children are null, print the answer string.

If not, call printTree recursively for the left, center, and right children, in that order.

Parameters:

current - a reference to the tree node

answer - a string

public class Node {

// Letter value, package private

char letter;

// Child nodes (left, center, right)

// Make sure these references are package private (like the letter value, above)

// YOUR CODE HERE

public Node(char letter) {

this.letter = letter;

}

}

--------------------------------------------------------------------------------------------------------------

import java.util.Arrays; import java.util.LinkedList; import java.util.Queue;

public class PQ4 {

// Instance variables for PQ4 static Node root;

public static void main(String[] args) {

// Test code for readTokens char[] letters = {'c','a','o','u','d','n','r','g','p','w','b','r','t'}; System.out.println("Letters: " + Arrays.toString(letters));

// Test code for buildTree buildTree(letters);

// Test code for traverseTree System.out.println("Words: "); printTree(root, "");

}

/** * Add letters to ternary tree using a level-order traversal (breadth first search). *

* Take a moment to look over the setup code and implement the while loop. *

*
1. Remove a node, curr, from the {@code Queue} and assign it into a temporary variable *
2. Assign the next three letters to curr's left, center, and right children. *
3. Add the children into the queue in the same order as above. *

* You can assume that {@code char[] letters} will always contain {@code i * 3 + 1} letters. * * @param letters an array of letters */ static void buildTree(char[] letters) { int index = 0; root = new Node(letters[index++]); Queue nextNode = new LinkedList<>(); nextNode.add(root); while(index < letters.length) { // YOUR CODE HERE } }

/** * Traverse the tree using recursion and print the letters contained in * every path from the root to a leaf node. *

* Follow this algorithm: *

*
1. If the node specified is null, return immediately. * This is a base case. *
2. Add the letter contained in the current node * to the answer string. *
3. Check whether the node is a leaf node (if all children * references are null). *
4. If all children are null, print the answer string. *
5. If not, call printTree recursively for the left, center, * and right children, in that order. *

* @param current a reference to the tree node * @param answer a string */ static void printTree(Node current, String answer) { // YOUR CODE HERE

} }