java - 树的分区压缩以及如何将节点压缩到根

Question

我试图通过让它们指向传递给的参数节点的根来压缩给定节点的所有祖先

 private E compressToRoot (E e) throws IllegalArgumentException;

例如，在上图中，如果我执行 compressToRoot(D)，则 D 将直接指向 A，C 将直接指向 A。如果参数和根之间还有其他节点，那么它们都将指向 A。

所有标签和箭头都存储在两个单独的地图中：

private Map<E,E>       parentMap   = new HashMap<E,E>(); //labels + arrows

我可以通过 (1) 将 D 和根之间的所有节点保存在一个集合中来完成此方法。(2) 让设置的所有元素指向（使父）根 (3) 返回根。

但是，我被困在如何遍历这张地图以到达根部。所以，对于这种方法，我会按照以下方式做一些事情

private E compressToRoot (E e) throws IllegalArgumentException {
    Set<E> collectLables = new HashSet<E>();
E root = null;

//get root.
for (E cycle : parentMap.keys()) {
    while (parentMap.get(e) != e) 
        e = parentMap.get(e);
        if (parentMap.get(e) == e)
            root = cycle;
 }


//collect all labels from parameter to root.
for (E element : parentMap.keys()) {
    while (parentMap.get(e) != root) {
        collectLables.add(element);
    }   
}


}

但是我不确定如何循环通过给定节点的父节点一直到根节点。

Answer 1

根据地图的效率，对上述 rambo 编码器的答案有轻微的潜在改进。ArrayList只需遍历路径两次，您就可以在不使用额外内存和开销的情况下做到这一点：

private E compressToRoot(E cursor) {
    E cursor2 = cursor;
    E node = parentMap.get(cursor);
    while (node != cursor)  {
        cursor = node;
        node = parentMap.get(node);
    }
    // Now cursor (and node) are the root.    

    node = parentMap.get(cursor2);
    while (node != cursor2) {
        parentMap.set(cursor2, cursor);
        cursor2 = node;
        node = parentMap.get(node);
    }

    return cursor;
}

Answer 2

我被困在如何遍历这张地图以到达根部。

看来您对“根”的定义是唯一指向自身的节点。它不是特别有效，但您可以只寻找这样的元素：

E findRoot(Map<E, E> parentMap) {
    for (Map.Entry<E, E> entry: parentMap.entrySet() {
        if (entry.key().equals(entry.value()) {
            return entry;
        }
    }

    // parentMap is empty, or the graph is corrupted
    // handle this edge case however you want
    return null;
}

Answer 3

递归很漂亮，但如果到根的最长路径的长度可能会变大，则支持迭代方法。你不想用完堆栈。

private E compressToRoot(E node) {
    if (parentMap.get(node) != node)
        parentMap.set(node, compressToRoot(node));
    return parentMap.get(node);
}

private E compressToRoot(E cursor) {
    E node;
    ArrayList<E> nodes = new ArrayList<E>();
    while ((node = parentMap.get(cursor)) != cursor)  {
        nodes.add(cursor);
        cursor = node;
    }

    for (node : nodes)
        parentMap.set(node, cursor);

    return cursor;
}