algorithm - 高效遍历单向树

Question

我有一个单向对象树，其中每个对象都指向其父对象。给定一个对象，我需要获取它的整个后代子树，作为对象的集合。这些对象实际上不在任何数据结构中，但我可以轻松获得所有对象的集合。

天真的方法是检查批处理中的每个对象，看看给定的对象是否是祖先，然后将其放在一边。这不会太有效......它带来了 O(N*N) 的开销，其中 N 是对象的数量。

另一种方法是递归方法，即搜索对象的直接子对象并为下一层重复该过程。不幸的是，这棵树是单向的……没有直接的方法来处理 child ，这只会比以前的方法稍微便宜一点。

我的问题:我在这里忽略了一个有效的算法吗？

谢谢，

尤瓦尔=8-)

Answer 1

正如其他人所提到的，构建对象的哈希表/映射到它们的(直接)子级列表。

从那里您可以轻松地查找“目标对象”的直接子对象列表，然后为列表中的每个对象重复该过程。

下面是我在 Java 中如何使用泛型，使用队列而不是任何递归:

public static Set<Node> findDescendants(List<Node> allNodes, Node thisNode) {

    // keep a map of Nodes to a List of that Node's direct children
    Map<Node, List<Node>> map = new HashMap<Node, List<Node>>();

    // populate the map - this is O(n) since we examine each and every node
    // in the list
    for (Node n : allNodes) {

        Node parent = n.getParent();
        if (parent != null) {

            List<Node> children = map.get(parent);
            if (children == null) {
                // instantiate list
                children = new ArrayList<Node>();
                map.put(parent, children);
            }
            children.add(n);
        }
    }


    // now, create a collection of thisNode's children (of all levels)
    Set<Node> allChildren = new HashSet<Node>();

    // keep a "queue" of nodes to look at
    List<Node> nodesToExamine = new ArrayList<Node>();
    nodesToExamine.add(thisNode);

    while (nodesToExamine.isEmpty() == false) {
        // pop a node off the queue
        Node node = nodesToExamine.remove(0);

        List<Node> children = map.get(node);
        if (children != null) {
            for (Node c : children) {
                allChildren.add(c);
                nodesToExamine.add(c);
            }
        }
    }

    return allChildren;
}

如果我记得如何正确计算的话，预计执行时间介于 O(n) 和 O(2n) 之间。您一定会查看列表中的每个节点，再加上一些操作来查找您节点的所有后代 - 在最坏的情况下(如果您在根节点上运行算法)您正在查看中的每个节点列表两次。