I am stuck on one of my university labs about Trees and hoping someone can help me figure this out. They have asked us to write a method called maxDegree() which returns the largest number of children of any node. I am struggling to figure out how to implement this, if anyone could look at my current method and point me in the right direction that would be great!
Diagram of example tree - https://i.sstatic.net/XZ3bl.jpg
package week10;
import java.util.*;
/**
* Skeleton of the recursive implementation of a general tree.
*
* @author Michael Albert
* @param <T> The type of values stored in the tree.
*/
public class Tree<T> {
private T rootValue;
private List<Tree<T>> children;
public Tree(T rootValue, List<Tree<T>> children) {
this.rootValue = rootValue;
this.children = children;
}
public Tree(T rootValue) {
this(rootValue, new ArrayList<Tree<T>>());
}
public int size() {
int count = 1;
for (Tree<T> child : children) {
count += child.size();
}
return count;
}
//METHOD I AM STUCK ON
public int maxDegree() {
int largestNode = 0;
for (Tree<T> child : children) {
child.maxDegree();
if (child.size() > largestNode) {
System.out.println("test" + children.size());
largestNode = child.size();
}
}
return largestNode;
}
public void add(Tree<T> child) {
children.add(child);
}
public Tree<T> find(T value) {
if (rootValue.equals(value)) {
return this;
}
for (Tree<T> child : children) {
Tree<T> match = child.find(value);
if (match != null) {
return match;
}
}
return null;
}
public List<T> postOrder() {
// implement this method
return new ArrayList<T>();
}
public String toString() {
if (children.isEmpty()) {
return rootValue.toString();
}
return rootValue.toString() + ' ' + children.toString();
}
public String toIndentedString() {
// implement this method
return "Not implemented yet!";
}
/** A helper method for testing (used by main). Searches tree for
* the given target and adds white space separated children to
* the tree matching target if there is one.
*
* @param target the root value to seach for.
* @param children a white space separated list of children to add
* to the tree whose value matches target.
*/
private static void addChildren(String target, String children) {
Tree<String> parent = tree.find(target);
if (parent != null) {
for (String child : children.split(" ")) {
parent.add(new Tree<>(child));
}
}
}
/** A tree instance used for testing. */
private static Tree<String> tree;
/**
* Entry point of the program (used for testing).
*
* @param args command line arguments are not used.
*/
public static void main(String[] args) {
System.out.println("Creating tree\n-------------");
tree = new Tree<>("food");
System.out.print(tree + "\nsize: " + tree.size());
System.out.println(", max degree: " + tree.maxDegree());
System.out.println("\nAdding children\n----------------");
addChildren("food", "meat fruit vegetable");
System.out.print(tree + "\nsize: " + tree.size());
System.out.println(", max degree: " + tree.maxDegree());
System.out.println("\nAdding deeper children\n----------------------");
addChildren("meat", "chicken beef fish");
addChildren("fish", "salmon cod tuna shark");
addChildren("vegetable", "cabbage");
System.out.print(tree + "\nsize: " + tree.size());
System.out.println(", max degree: " + tree.maxDegree());
System.out.println("\nPostorder\n---------");
System.out.println(tree.postOrder());
System.out.println("\nIndented string\n---------------");
System.out.print(tree.toIndentedString());
}
}
size()function returns the count of all the children of that node, but for themaxDegree()you only need the count of the immediate children