按节点具有的 child-nodes 数量对无序树进行排序

Question

我目前正在独自学习 Robert Sedgewick 的 "Algorithms in java"（第 3 版，德文版），我正在尝试解决那里的一个练习，目前是 "creative-solutions"-部分。

作为一个练习的解决方案的一部分，我试图根据每个节点的 children 数量对未排序的树进行排序，children 数量较大的节点排在第一位：

根据child-nodes自身拥有的child-nodesnNodes的数量，对parentn0的所有child-nodes进行排序，从左到右排序从大到小。对树中的所有节点执行此排序。
如果这child-nodes中的2sibling-nodesn1和n2有相同的nNodes，则去n1和n2的child-nodes尝试将这两个按照nNodes 他们最大的 children。如果没有发现差异，尝试按照nNodes他们第2大的children等排序
如果你运行出children，去2中child的child-nodechildren和重复 2. 等等
如果经过比较发现n1和n2都是形状相同的树的根，则两者谁在前无关紧要。

为了进行视觉比较，此 "rule" 将导致如下所示的树排序：Example of Sorting。

代码

我遇到的问题是正确执行排序。每棵树都由节点组成。每个 Node 包含一个值（这样你就有一个 "name" 的节点，对于排序本身并不重要，排序本身只关心每个节点的 children 的数量）和一个 [=58 的 arrayList =] 到该节点的 child-nodes。对于没有 children 的节点，ArrayList 的大小为 0。这里的关键是对所有节点中的 ArrayList 进行排序，我目前正在尝试使用 built-in 排序方法和比较器 object。我想我必须递归地处理这个问题，这让整个事情变得非常混乱，因为我目前有一个比较器方法调用自身，同时也在同一方法中为其他 ArraLists 调用 "sort" 。当我在某些 main-methods 中尝试使用下面的 sortForest 方法进行测试时，它会出现 stack-overflow 错误。

    static NodeComparator comp = new NodeComparator();

    static class Node {
        int value;
        ArrayList<Node> children;

        Node(int value, ArrayList<Node> children) {
            this.value = value;
            this.children = children;
        }
    }

    static class NodeComparator implements Comparator<Node> {
        public NodeComparator() {
        }

        public int compare(Node n1, Node n2) {
            /*-
             * Base Case 1: Both Nodes are leafs (isEmpty() is true) - they are
             * equal -> return 0.
             * Base Case 2/3: One of the Nodes is a leaf while the other isn't - 
             * the one that is a leaf is "lower" than the one that isn't. ->
             * return (-) 1. 
             */
            if (n1.children.isEmpty() && n2.children.isEmpty()) {
                return 0;
            } else if (n2.children.isEmpty()) {
                n1.children.sort(comp);
                return 1;
            } else if (n1.children.isEmpty()) {
                n2.children.sort(comp);
                return -1;
            } else {
                /* Get the amount of children the 2 nodes n1 and n2 have */
                int nChildren1 = (n1.children.isEmpty()) ? 0 : n1.children.size();
                int nChildren2 = (n2.children.isEmpty()) ? 0 : n2.children.size();
                /* Always sort the ArrayList of children that they have */
                n1.children.sort(comp);
                n2.children.sort(comp);

                /*
                 * If n1 and n2 have equal amounts of children, compare the
                 * amounts of children their children have, from largest to
                 * lowest
                 */
                if (nChildren1 == nChildren2) {
                    int result = 0;
                    for (int i = 0; (i < nChildren1) && (result == 0); i++) {
                        compare(n1.children.get(i), n2.children.get(i));
                    }
                    return result;
                } else {
                    /*- If one node has more children than the other, sort accordingly */
                    return ((nChildren1 > nChildren2) ? 1 : -1);
                }
            }
        }
    }

    static void sortForest(Node root) {
        for (int i = 0; i < root.children.size(); i++) {
            sortForest(root.children.get(i));
            root.children.sort(comp);
        }
        return;
    }

问题

如何让这段代码工作？我有点确定这大致在正确解决方案的范围内，但我已经尝试思考了几个小时，但无法找出一个。我确信这给了我 stack-overflows，因为 never-ending 递归在某处，我只是看不到它。一般来说，递归给我带来了问题，无法在心理上正确地做到这一点。我找不到与此相同的问题，那些类似的问题与二叉树而不是无序树有关。

Answer 1

根据树的大小，您可能运行在调用 sortForest 关于 Java 的默认堆栈大小时受到限制。解决方法包括通过 -Xss JVM 选项增加它，在 Thread constructor, re-writing it non-recursive or using the Trampoline pattern.

中设置堆栈大小

Answer 2

上面的代码有几处错误：

代码假定每棵树的根节点不包含对自身的引用（上面代码中未显示），这本来导致比较方法一次又一次地调用根，这已得到纠正。
在比较方法中调用排序是完全没有必要的，实际上是错误的。代码已经为每个具有 sortForest() 的节点调用排序方法，从叶子开始，因此那里没有位置，需要从比较方法代码的所有部分中删除。
对于给定的return，compare方法不会导致从大到小的排序，而是从小到大的排序。它需要 return 1 它 returns -1 反之亦然。
compare方法也需要在其for循环中，将compare()的return存入result，否则结果永远不会改变，循环也不会一旦发现不相似就停止。
sortForest() 中 root.children.sort(comp); 的排序绝对必须发生在 forLoop 之外，否则你对 ArrayList 的某些部分进行排序，而您仍然需要它们按原来的顺序正确执行所有调用。

纠正所有这些问题后，上面的 sortForest() 和 compare() 方法为示例树提供了正确的排序结果：

int[] tree1 = { 2, 3, 3, 3, 2, 2, 1, 0, 7, 5, 3, 10, 10, 6 };

int[] tree2 = { 4, 10, 11, 0, 4, 0, 12, 4, 7, 8, 0, 3, 4, 12 };

并按照 this picture 所示对它们进行排序。

可以找到解决方案的完整代码以及一些优化和删除不必要的代码以及固定排序here

按节点具有的 child-nodes 数量对无序树进行排序

Sort an unordered tree by the amount of child-nodes a node has

java

stack-overflow

sorting

tree