TreeView - 如何计算所有子项的数量（包括折叠的）

Question

有没有一种方法可以获取TreeView对象中子项的数量？我想计算所有子项的数量，包括孙子级别的子项。

getExpandedItemCount()方法只能获取已展开的子项数。是否有一种方法可以获取所有子项的数量，无论它们是否已展开。

- john

Answer 1

对于只需计算小树节点数量的问题而言，本答案提供的解决方案是过于复杂了。其他答案中提供的简单递归计数解决方案已经足够。本答案提供的内容只是为了增加一些背景和备选实现。

关于栈和递归

当你使用递归时，你隐含地依赖于Java运行时为你维护一个项的堆栈。对于非常大的树，这可能成为一个问题，因为运行时可能会耗尽堆栈空间（堆栈溢出）。

有关更多关于优先使用堆栈而不是递归的信息请参见：

• Java: Stackoverflow in finite recursion上John Skeet的回答。
• Top coder tree traversal algorithms, depth first search.

当然，如果你知道正在处理的树很小，那么使用递归是可以的。有时递归算法比它们的非递归对应算法更容易理解。

基于迭代器的解决方案

private class TreeIterator<T> implements Iterator<TreeItem<T>> {
    private Stack<TreeItem<T>> stack = new Stack<>();

    public TreeIterator(TreeItem<T> root) {
        stack.push(root);
    }

    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    @Override
    public TreeItem<T> next() {
        TreeItem<T> nextItem = stack.pop();
        nextItem.getChildren().forEach(stack::push);

        return nextItem;
    }
}

使用迭代器遍历树并计算其中的元素数量。

TreeIterator<String> iterator = new TreeIterator<>(rootItem);
int nItems = 0;
while (iterator.hasNext()) {
    nItems++;
    iterator.next();
}

如果需要，可以通过创建自定义流支持类将迭代器适配为流，从而使您能够编写如下的函数式代码：

iterator can be adapted to a stream

TreeItemStreamSupport.stream(rootItem)
    .filter(TreeItem::isExpanded)
    .count()

示例程序

import javafx.application.Application;
import javafx.geometry.Insets;
import javafx.scene.Scene;
import javafx.scene.control.*;
import javafx.scene.layout.VBox;
import javafx.stage.Stage;

import java.util.*;
import java.util.stream.*;

public class TreeViewSample extends Application {

    // limits on randomly generated tree size.
    private static final int MAX_DEPTH = 8;
    private static final int MAX_CHILDREN_PER_NODE = 6;
    private static final double EXPANSION_PROPABILITY = 0.2;

    public static void main(String[] args) {
        launch(args);
    }

    @Override
    public void start(Stage stage) {
        Label numItemsLabel = new Label();

        // create a tree.
        TreeItem<String> rootItem = TreeFactory.createTree(
                MAX_DEPTH,
                MAX_CHILDREN_PER_NODE,
                EXPANSION_PROPABILITY
        );
        rootItem.setExpanded(true);
        TreeView<String> tree = new TreeView<>(rootItem);

        numItemsLabel.setText(
            "Num Items: " + countExpandedItemsUsingStream(rootItem)
        );

        // display the number of items and the tree.
        VBox layout = new VBox(10, numItemsLabel, tree);
        layout.setPadding(new Insets(10));

        stage.setScene(new Scene(layout, 300, 250));
        stage.show();
    }

    // unused method demonstrating alternate solution.
    private long countItemsUsingIterator(TreeItem<String> rootItem) {
        TreeItemIterator<String> iterator = new TreeItemIterator<>(rootItem);

        int nItems = 0;
        while (iterator.hasNext()) {
            nItems++;
            iterator.next();
        }

        return nItems;
    }

    private long countExpandedItemsUsingStream(TreeItem<String> rootItem) {
        return
                TreeItemStreamSupport.stream(rootItem)
                        .filter(TreeItem::isExpanded)
                        .count();
    }

    // unused method demonstrating alternate Jens-Peter Haack solution.
    private long countItemsUsingRecursion(TreeItem<?> node) {
        int count = 1;

        for (TreeItem child : node.getChildren()) {
            count += countItemsUsingRecursion(child);
        }

        return count;
    }

    /**
     * Random Tree generation algorithm.
     */
    private static class TreeFactory {
        private static final Random random = new Random(42);

        static TreeItem<String> createTree(
                int maxDepth,
                int maxChildrenPerNode,
                double expansionProbability
        ) {
            TreeItem<String> root = new TreeItem<>("Root 0:0");
            Stack<DepthTreeItem> itemStack = new Stack<>();
            itemStack.push(new DepthTreeItem(root, 0));

            while (!itemStack.isEmpty()) {
                int numChildren = random.nextInt(maxChildrenPerNode + 1);

                DepthTreeItem nextItem = itemStack.pop();
                int childDepth = nextItem.depth + 1;

                for (int i = 0; i < numChildren; i++) {
                    TreeItem<String> child = new TreeItem<>(
                        "Item " + childDepth + ":" + i
                    );
                    child.setExpanded(random.nextDouble() < expansionProbability);
                    nextItem.treeItem.getChildren().add(child);
                    if (childDepth < maxDepth) {
                        itemStack.push(new DepthTreeItem(child, childDepth));
                    }
                }
            }

            return root;
        }

        static class DepthTreeItem {
            DepthTreeItem(TreeItem<String> treeItem, int depth) {
                this.treeItem = treeItem;
                this.depth = depth;
            }
            TreeItem<String> treeItem;
            int depth;
        }
    }
}

/**
 * Provide a stream of tree items from a root tree item.
 */
class TreeItemStreamSupport {
    public static <T> Stream<TreeItem<T>> stream(TreeItem<T> rootItem) {
        return asStream(new TreeItemIterator<>(rootItem));
    }

    private static <T> Stream<TreeItem<T>> asStream(TreeItemIterator<T> iterator) {
        Iterable<TreeItem<T>> iterable = () -> iterator;

        return StreamSupport.stream(
                iterable.spliterator(),
                false
        );
    }
}

/**
 * Iterate over items in a tree.
 * The tree should not be modified while this iterator is being used.
 *
 * @param <T> the type of items stored in the tree.
 */
class TreeItemIterator<T> implements Iterator<TreeItem<T>> {
    private Stack<TreeItem<T>> stack = new Stack<>();

    public TreeItemIterator(TreeItem<T> root) {
        stack.push(root);
    }

    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    @Override
    public TreeItem<T> next() {
        TreeItem<T> nextItem = stack.pop();
        nextItem.getChildren().forEach(stack::push);

        return nextItem;
    }
}

- jewelsea

---

感谢您提供这个例子。我想指出的是，按照目前的情况，最后一个子元素将会出现在堆栈的顶部。我建议在调用forEach之前从getChildren()中反转列表。注意，作为一名Groovyist，我会简单地使用reverse()来完成这个操作，但肯定有一种不错的Java方法。 - mike rodent

Answer 2

没有提供一种计算树中所有子节点数量的方法，这是有充分理由的，因为展开后的树可能非常庞大甚至无限。

例如：可以显示实数的所有数字的树：

static class InfiniteNumberItem extends TreeItem<String> {
    boolean expanded = false;
    public InfiniteNumberItem(String name) {
        super(name);
    }

    @Override public ObservableList<TreeItem<String>> getChildren() {
        if (!expanded) {
            for (int i = 0; i < 10; i++)  {
                super.getChildren().add(new InfiniteNumberItem(""+i));
            }
            expanded = true;
        }
        return super.getChildren();
    }
    @Override public boolean isLeaf() {
        return false;
    }
}

void testTreeInfinite(VBox box) { 
    TreeView<String> tree = new TreeView<String>();
    tree.prefHeightProperty().bind(box.heightProperty());

    tree.setRoot(new InfiniteNumberItem("3."));
    box.getChildren().add(tree);
}

但是如果你知道自己在做什么，并且树的大小是有限制的，那么你就需要自己计算：

int count(TreeItem<?> node) {
    int count = 1;
    for (TreeItem child : node.getChildren()) {
        count += count(child);
    }
    return count;
}

- Jens-Peter Haack

Answer 3

使用递归，类似以下方式：

private static <T> long countChildren(TreeItem<T> treeItem) {
    long count = 0;

    if (treeItem != null) {
        ObservableList<TreeItem<T>> children = treeItem.getChildren();

        if (children != null) {
            count += children.size();

            for (TreeItem<T> child : children) {
                count += countChildren(child);
            }
        }
    }

    return count;
}

为了在计数中包含根节点，请加1：

long count = countChildren(treeItem) + 1;

然后只需要调用该方法并将根作为参数传递即可：

System.out.println(countChildren(treeView.getRoot()));

- jmn