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

Question

我试图压缩给定节点的所有祖先，方法是让它们指向传递给的参数节点的根

 private E compressToRoot (E e) throws IllegalArgumentException;

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

所有的标签和箭头都存储在两个单独的 map 中:

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

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

但是，我对如何遍历此 map 以到达根目录一筹莫展。因此，对于该方法，我会按照以下方式做一些事情

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

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

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;
}