java - 构建叶图 - 成对的祖先列表(父 - 子)

Question

我有一个树结构，我需要以 map 的形式表示，键是叶子，值是叶子祖先的列表(祖先的顺序并不重要)。

例如，像这样的树:

      1
     / \
    2   3
   / \
  4   5
 /
6

会变成这样:

6 -> [4, 2, 1]
5 -> [2, 1]
3 -> [1]

为了构建这张 map ，我得到了一对( parent ， child )的列表。

对于示例树，我将以没有特定顺序的方式给出:

1, 2
1, 3
2, 4
2, 5
4, 6

一个更好理解的执行示例:

起初， map 是空的。我得到 2、4。

map 包含 4 -> [2]。我得到 2、5。

map 包含 4 -> [2]、5 -> [2]。我得到了 4、6。

map 包含 6 -> [4, 2], 5 -> [2]。我得到 1、3。

map 包含 6 -> [4, 2], 5 -> [2], 3 -> [1]。我得到了 1、2。

map 包含 6 -> [4, 2, 1], 5 -> [2, 1], 3 -> [1]。

想出了一些东西，但是感觉比较臃肿，难以理解。 某些特定的输入顺序也是错误的:

1, 3
4, 6
1, 2
2, 4
2, 5

产量

6 -> [4, 2, 1]
5 -> [4, 2, 1]
3 -> [1]

代码:

updateMap(long parent, long child) {
    if (map.isEmpty()) {
        map.put(child, Sets.newHashSet(parent));
    } else {
        Set<Long> flattenedValues = new HashSet<Long>();
        for (Set<Long> set : map.values()) {
            flattenedValues.addAll(set);
        }
        if (flattenedValues.contains(child)) {
            for (Long key : getKeysByValue(map, child)) {
                map.get(key).add(parent);
            }
            if (map.containsKey(parent)) {
                for (Long key : getKeysByValue(map, parent)) {
                    Set<Long> toAdd = new HashSet<Long>();
                    toAdd.add(parent);
                    toAdd.addAll(map.remove(parent));
                    map.get(key).addAll(toAdd);
                }
            }
        } else {
            if (map.containsKey(parent)) {
                map.put(child, Sets.newHashSet(parent));
                map.get(child).addAll(
                        map.remove(parent));
            } else {
                map.put(child, Sets.newHashSet(parent));
                for (Long key : getKeysByValue(map, parent)) {
                    map.get(child).addAll(map.get(key));
                }
            }
        }
    }
}

我确信有更好的方法来做我想做的事，你能帮我吗？谢谢!

Answer 1

使用数组可以很容易地解决这个问题。将有 2 个非常有用的数组。

isLeaf:这个数组将存储 boolean 值并判断一个节点是否是叶节点。最初所有值都为真。

每当输入一对时，第一个元素的值将设置为 false，因为它有一个子元素。

parent:该数组将存储节点父节点的值。最初所有值都设置为 -1，每当输入一对时，都会设置该对的第二个元素的父值到第一个元素。

基本思路:解决这个问题的思路非常简单优雅。

基本上我们遍历节点，对于所有叶子节点，我们使用父数组列出它们的祖先，终止条件也非常简单，因为我们只会在到达根节点时停止，并且对于根节点只有父节点设置为-1

import java.util.*;
class Tree
{
 public static void main(String []args)
 {
     int n,i,p,j,c,pairs;
     Scanner sc=new Scanner(System.in);
     System.out.println("enter the number of elements in tree");
     n=sc.nextInt();
     boolean []isLeaf=new boolean[n];
     int []parent=new int[n];     
     for(i=0;i<n;++i)
     {
          isLeaf[i]=true;
          parent[i]=-1;
     }
     System.out.println("Enter the number of  pairs");
     pairs=sc.nextInt();
     System.out.println("now enter pairs like 1 2(separate them by space)");
     for(i=0;i<pairs;++i)
     {
         p=sc.nextInt();
         c=sc.nextInt();
         isLeaf[p-1]=false;
         parent[c-1]=p-1;
     }     
     for(i=0;i<n;++i)
      if(isLeaf[i])
      {
          j=i;
          System.out.println("\nthe ancestors of "+(i+1)+" are");
          while(parent[j]!=-1)
           {System.out.print((parent[j]+1)+" ");j=parent[j];}
      }
 }
}