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

前端之家收集整理的这篇文章主要介绍了java – 在特定树编码中获取从根到叶的路径前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

我有一个表示为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]
原文链接:https://www.f2er.com/java/437868.html

猜你在找的Java相关文章