Untitled
unknown
java
2 years ago
3.2 kB
6
Indexable
package comp1110.lab9; import java.util.ArrayList; import java.util.LinkedList; import java.util.Objects; public class FamilyTree { /** * This function accepts an Individual <code>ancestor</code> representing * the root (common ancestor) of a family tree * and the name of a target individual to find within that family tree, * and returns a string representation of all the ancestors of that * individual, each separated by the string " born of ". * <p> * If target name matches the name of <code>ancestor</code>, then only * the target name is returned. * <p> * If the target name is not found within the family tree descended from * <code>ancestor</code>, then null is returned. * <p> * For example, given an Individual homer representing a person named * "Homer", who has children named "Lisa" and "Bart": * getAncestry(homer, "Lisa") returns "Lisa born of Homer"; * getAncestry(homer, "Bart") returns "Bart born of Homer"; and * getAncestry(homer, "Homer") returns "Homer"; and * getAncestry(homer, "Barney") returns null * <p> * Note: each individual has only one parent in the family tree. * * @param ancestor the root (common ancestor) of a family tree * @param targetName the name of an individual to find in the family tree * @return a String representing the ancestry of the individual named * <code>targetName</code>, or null if no such individual is found */ public static String getAncestry(Individual ancestor, String targetName) { LinkedList<Individual> path = new LinkedList<>(); boolean success = dfs(ancestor, targetName, path); if (!success) { return null; } StringBuilder stringBuilder = new StringBuilder(); for (int index = 0; index < path.size(); index++) { stringBuilder.append(path.get(index).name); if (index != path.size() - 1) { stringBuilder.append(" born of "); } } return stringBuilder.toString(); } public static boolean dfs(Individual node, String targetName, LinkedList<Individual> path) { if (node == null) { return false; } path.push(node); if (node.name.equals(targetName)) { return true; } if (node.children != null) { for (var child : node.children) { if (dfs(child, targetName, path)) { return true; } } } path.pop(); return false; } /** * This class represents an individual with zero or more children. */ static class Individual { public String name; /** * This individual's immediate descendants. * If this individual has no children, this field is null. */ public Individual[] children; public Individual(String name, Individual[] children) { this.name = name; this.children = children; } } }
Editor is loading...