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

Question

我有一棵树代表 Set<Integer>[]

以下内容Set<Integer>[]:

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

代表以下树:

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

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

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

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

Answer 1

在树中搜索的关键通常是实现一个良好的邻接函数，该函数给出特定节点的相邻节点。

对于这棵树，邻接函数需要找到该节点位于哪一层，然后返回下一层的节点作为相邻节点。它看起来像这样：

  /**
   * 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<Integer> getAdjacentsToNode(Integer node) {

    for (int i = 0; i < tree.size(); i++) {
      Set<Integer> level = tree.get(i);
      if (level.contains(node) && i < tree.size() - 1) {
        return tree.get(i + 1);
      }
    }
    return null;
  }

假设我们已经将树定义为类中的字段。

在运行搜索之前，我们需要适当地初始化设置根并对路径进行一些准备工作。因此我们执行以下操作：

/**
 * 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 搜索，在遍历树时将每个节点附加到当前路径，并将该路径添加到我们设置的路径中，并在到达死胡同（叶子）时重置它：

  /**
   * 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<Integer> currentPath = new ArrayList<Integer>();
  private List<Integer[]> paths = new ArrayList<Integer[]>();
  private ArrayList<Set<Integer>> tree;
  private Integer root;
  /**
   * constructor
   * @param tree
   */
  public DFS(ArrayList<Set<Integer>> tree) { 
    this.tree = tree;
  }

  public List<Integer[]> getPaths() {
    return paths;
  }
  public void setPaths(List<Integer[]> paths) {
    this.paths = paths;
  }
  public Integer getRoot() {
    return root;
  }
  public void setRoot(Integer root) {
    this.root = root;
  }

/**
 * 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);
  }

  /**
   * 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<Integer> getAdjacentsToNode(Integer node) {

    for (int i = 0; i < tree.size(); i++) {
      Set<Integer> level = tree.get(i);
      if (level.contains(node) && i < tree.size() - 1) {
        return tree.get(i + 1);
      }
    }
    return null;
  }

  /**
   * 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);
    }
  }
}

为了测试它，我们尝试这样做：

public static void main(String[] args) { 
    ArrayList<Set<Integer>> tree = new ArrayList<Set<Integer>>();
    Set<Integer> level1 = new HashSet<Integer>();
    level1.add(new Integer(1));

    Set<Integer> level2 = new HashSet<Integer>();
    level2.add(new Integer(2));
    level2.add(new Integer(3));

    Set<Integer> level3 = new HashSet<Integer>();
    level3.add(new Integer(4));

    Set<Integer> level4 = new HashSet<Integer>();
    level4.add(new Integer(5));
    level4.add(new Integer(6));
    level4.add(new Integer(7));

    tree.add(level1);
    tree.add(level2);
    tree.add(level3);
    tree.add(level4);

    DFS dfsSearch = new DFS(tree); 
    dfsSearch.initialize();
    dfsSearch.runDFS(dfsSearch.getRoot());

    for (Integer[] path : dfsSearch.getPaths()) { 
      System.out.println(Arrays.toString(path));
    }

我们得到以下输出：

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