Pobieranie ścieżki od korzenia do liści w określonym kodowaniu drzewa

Question

Mam drzewa reprezentowany jako Set<Integer>[]

następujących Set<Integer>[]:

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

reprezentuje następujące drzewa:

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

So każdy poziom w drzewie jest kodowany jako Set. Cały zestaw dzieci na określonym poziomie w drzewie jest taki sam. W pierwszym zestawie może być więcej niż jedna liczba całkowita.

chcę get z Set<Integer>[], listę wszystkich ścieżek z korzenia do liści:

[ [ 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

Klucz do wyszukiwania w drzewach jest zwykle wykonawczego dobra funkcja Ajacency, która daje sąsiednie węzły dla określonego węzła.

Dla tego drzewa funkcja przylegania chce znaleźć poziom, na którym leży węzeł, a następnie zwrócić węzły na wyższym poziomie jako przylegające. Będzie to wyglądać mniej więcej tak:

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

Zakładając, że mamy już drzewo zdefiniowany jako pole w klasie.

Zanim przejdziemy do naszych poszukiwań, chcielibyśmy zainicjować odpowiednie ustawienie katalogu głównego i wykonać pewne wstępne kroki na ścieżkach. Dlatego należy wykonać następujące czynności:

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

Zakładając, że currentPath i root są już zdefiniowane jako pola.

Następnie możemy uruchomić wyszukiwanie DFS na drzewie dołączając każdego węzła do naszej aktualnej ścieżki jak przemierzać drzewem, dodając, że ścieżkę do naszego układu ścieżek i resetowanie go, gdy docieramy do ślepego (Skrzydła):

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

cała klasa zatem wygląda następująco:

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

By to sprawdzić, to spróbuj tego:

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

i otrzymujemy następujące dane wyjściowe:

[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 2

Nie zamierzam napisać kod, ale najprostszym sposobem będzie głębokość pierwszy traversal, gdzie na każdym poziomie dodajesz każdy wpis do bieżących ścieżek.

Twoja wartość zwracana będzie również zbiorem (lub tablicą) list (ponieważ pionowa ścieżka nie może być zbiorem nieuporządkowanym).

w pseudo-kod:

def getPaths(levels) { 
    return getPaths(levels, 0, new Set()) 
} 

def getPaths(levels, currentIndex, paths) { 

    if(currentIndex == levels.length) 
    return paths 

    def newPaths = new Set(paths) 

    for(path : paths) { 
    for(level : levels) { 
     newPaths.add(path + level) 
    } 
    } 

    return getPaths(levels, currentIndex + 1, newPaths) 

} 

Answer 3

spróbować czegoś takiego:

public static List<Integer[]> getAllPaths(Set<Integer>[] tree){ 

    // Get the overall number of path 
    int totalSize = 1; 
    for(Set<Integer> line : tree){ 
     totalSize *= line.size(); 
    } 

    // Create the empty paths 
    List<Integer[]> allPaths = new ArrayList<Integer[]>(totalSize); 
    for(int i = 0 ; i<totalSize ; ++i){ 
     Integer[] path = new Integer[tree.length]; 
     allPaths.add(path); 
    } 

    // Fill the paths 
    int indexLine = 0; 
    for (Set<Integer> line : tree) { 
     Iterator<Integer[]> pathIterator = allPaths.iterator(); 
     Iterator<Integer> lineIterator = line.iterator(); 
     while(pathIterator.hasNext()){ 
      if(!lineIterator.hasNext()){ 
       lineIterator = line.iterator(); 
      } 
      pathIterator.next()[indexLine] = lineIterator.next(); 
     } 
     ++indexLine; 
    } 
    return allPaths; 
} 

To działa dla przykładu:

public static void main(String[] args) { 

    Set<Integer> line1 = new HashSet<Integer>(); 
    line1.add(new Integer(1)); 
    Set<Integer> line2 = new HashSet<Integer>(); 
    line2.add(new Integer(2)); 
    line2.add(new Integer(3)); 
    Set<Integer> line3 = new HashSet<Integer>(); 
    line3.add(new Integer(4)); 
    Set<Integer> line4 = new HashSet<Integer>(); 
    line4.add(new Integer(5)); 
    line4.add(new Integer(6)); 
    line4.add(new Integer(7)); 

    Set[] test = {line1, line2,line3,line4}; 

    List<Integer[]> allPaths = getAllPaths(test); 

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