Java - 树，返回 arrayList 中的最大节点数

Question

我被困在我的一个关于树的大学实验室里，希望有人能帮助我解决这个问题。他们要求我们编写一个名为 maxDegree() 的方法，该方法返回任何节点的最大子节点数。我正在努力弄清楚如何实现这一点，如果有人可以看看我当前的方法并为我指出正确的方向，那就太好了!

示例 TreeMap - http://imgur.com/eGqDpf2l.png

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());
    }

}

Answer 1

这会起作用:

public int maxDegree()
{
    // Get the number of immediate children
    int numChildren = this.children.size();

    // Find the max of all children
    int maxOfChildren = 0;
    for (Tree<T> child : children)
    {
        maxOfChildren = Math.max(maxOfChildren, child.maxDegree());
    }

    // return the greater of immediate child or max of children
    return Math.max(numChildren, maxOfChildren);
}

示例树的说明

1. 在食物节点上调用最大度数(它有 3 个直接子节点)
2. 我们循环遍历食物的所有子元素(肉类、水果、蔬菜)
3. 在肉节点上调用最大度数(它有 3 个直接子节点)
4. 我们循环遍历所有肉类子代(鸡肉、牛肉、鱼)
5. 在鸡节点上调用最大度数(它有 0 个直接子节点)
6. 鸡的最大度数为0
7. 在牛肉节点上调用最大度数(它有 0 个直接子节点)
8. 牛肉的最大等级为0
9. 在鱼节点上调用最大度数(它有 4 个直接子节点)
10. 我们循环遍历鱼类的所有子代(鲑鱼、鳕鱼、金枪鱼、鲨鱼)
11. 在鲑鱼节点上调用最大度数(它有 0 个直接子节点)
12. 鲑鱼的最大度数为 0
13. 在 cod 节点上调用 Max Degree(它有 0 个直接子节点)
14. cod 的最大度数为 0
15. 在 tuna 节点上调用 Max Degree(它有 0 个直接子节点)
16. 金枪鱼的最大度数为0
17. 在 shark 节点上调用 Max Degree(它有 0 个直接子节点)
18. 鲨鱼的最大等级为 0
19. 鱼的所有子代的最大度数为 0
20. 鱼的最大度数为 4
21. 所有肉子代的最大度数为 4
22. 最大肉度为 4
23. 在水果节点上调用最大度数(它有 0 个直接子节点)
24. 水果的最大度数为 0
25. 在蔬菜节点上调用最大度数(它有 1 个直接子节点)
26. 我们循环遍历蔬菜(卷心菜，)的所有子代
27. 在卷心菜节点上调用最大度数(它有 0 个直接子节点)
28. 卷心菜最大度数为 0
29. 所有蔬菜子代的最大度数为 0
30. 蔬菜度最大为1
31. 所有食物子级的最大度数为 4
32. 食物的最大度数为 4