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

Question

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

示例树示意图- 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. 我们循环遍历所有肉的子节点(鸡肉、牛肉、鱼、在鸡肉节点上调用立即children)
5. Max最大度(它有0立即鸡肉的children)
6. Max度是0)在牛肉节点上调用
7. 最大度(它有0立即牛肉度是0
8. 最大度在鱼节点上被调用(它有4个直接子)
9. 我们循环通过鱼的所有孩子(鲑鱼，鳕鱼，金枪鱼，鲨鱼，在鲑鱼节点上调用鲨鱼的最大度数(它具有0立即children)
10. Max度的鲑鱼是0
11. 最大度在鳕鱼节点上被调用(它具有0立即的鳕鱼度数是0
12. 最大度数在金枪鱼节点上被调用(它具有0金枪鱼的立即children)
13. Max度数为0
14. 最大度数在鲨鱼节点上被调用(它具有0立即的鲨鱼度数是0

在所有鱼的子节点中，鱼的最大度是4鱼的最大度是4

1. 肉的最大度是4
2. 最大度在水果节点上被调用(它具有0直接的水果度是0
3. 在蔬菜节点上被调用的最大度(它有1个直接子节点)
4. 我们循环通过蔬菜的所有子节点(卷心菜，)在卷心菜节点上调用
5. 最大度(它有0卷心菜的直接children)
6. Max度是0
7. 蔬菜的所有孩子的最大度是0
8. 蔬菜的最大度是1
9. 所有食物的最大度是4
10. 食物的最大度是4