java – 在特定树编码中获取从根到叶的路径

发布时间：2020-12-14 19:15:04 所属栏目：Java 来源：网络整理

导读：我有一个表示为Set []的树以下Set []： [ { 1 },{ 2,3 },{ 4 },{ 5,6,7 } ] 代表以下树： 1 / / / 2 3 | | 4 4 /| /|5 6 7 5 6 7 因此树中的每个级别都被编码为Set.树中特定级别的所有子集都是相同的.第一组中可以有多个整数. 我想从Set []中获取从

我有一个表示为Set< Integer> []的树

以下Set< Integer> []：

[ { 1 },{ 2,3 },{ 4 },{ 5,6,7 } ]

代表以下树：

      1
     / 
    /   
   /     
  2       3
  |       |
  4       4
 /|     /|
5 6 7   5 6 7

因此树中的每个级别都被编码为Set.树中特定级别的所有子集都是相同的.第一组中可以有多个整数.

我想从Set< Integer> []中获取从root到leaves的所有路径的列表：

[ [ 1,2,4,5 ],[ 1,6 ],7 ],3,7 ] ]

最佳答案

在树中搜索的密钥通常是实现良好的Ajacency函数,该函数为特定节点提供相邻节点.

对于此树,邻接函数将希望找到节点所在的级别,然后将下一级别的节点作为邻接返回.它看起来像这样：

  /**
   * This returns the adjacent nodes to an integer node in the tree
   * @param node
   * @return a set of adjacent nodes,and null otherwise
   */
  public Set


假设我们已经将树定义为类中的字段.
在我们运行搜索之前,我们希望适当地设置根目录并对路径做一些预备工作.因此,我们执行以下操作：

/**
 * initializes our search,sets the root and adds it to the path
 */
  public void initialize() {
    root = -1;
    for (Integer node : tree.get(0)) {
      root = node;
    }
    currentPath.add(root);
  }

假设currentPath和root已经定义为字段.
然后,当我们遍历树时,我们在树上运行DFS搜索,将每个节点附加到当前路径,并将该路径添加到我们的设置路径,并在到达deadend(叶子)时重置它：

  /**
   * runs a DFS on the tree to retrieve all paths
   * @param tree
   */
  public void runDFS(Integer node) {
    if (getAdjacentsToNode(node) != null) {
      for (Integer adjNode : getAdjacentsToNode(node)) {
        currentPath.add(adjNode);
        runDFS(adjNode);
      }
      currentPath.remove(currentPath.size() -1);
    } else {
      paths.add(currentPath.toArray(new Integer[0]));
      currentPath.remove(currentPath.size() -1);
    }
  }

因此,整个班级看起来像这样：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DFS {
  private List

为了测试它,我们试试这个：

public static void main(String[] args) { 
    ArrayList

我们得到以下输出：

[1,5]
[1,6]
[1,7]
[1,7]


                        （编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!