Найти путь к узлу в дереве?

Question

У меня есть класс дерева, который выглядит как:

Class Tree { 
    Node root; 
    Node curNode; 
    public List<String> find(String value) { 
     if (curNode == null) curNode = root; 
     for (Node child : curNode.children) { 
      if (found == false) { 
       if (child.data.equals(value)) { 
        // if it finds it return the path to this node. 
       } 
       curNode = child; 
       findDFS(value); 
      } 
     } 
    } 


class Node { 
    List<Node> children; 
    String data; 
} 

Где корень дерева содержит указатели на дочерние узлы, которые указывают на других детей и т.д. и т.п. Что у меня возникли проблемы с это, как только он находит узел, я необходимо вернуть путь к этому узлу.

Answer 1

Если узлы указывают только на своих детей, вам необходимо отслеживать каждый путь по пути вниз. Как упоминалось в комментарии, вы можете сделать это со своим собственным стеком или с рекурсией. Например, вы всегда можете вернуть вызов find() для дочерних элементов каждого узла.

Если узлы указывают в обоих направлениях, вы можете легко проследить путь до того, как найдете правильный узел.

Answer 2

Передача списка, отслеживающего путь, после нахождения узла, выхода из рекурсии и заполнения пути один за другим.

Boolean Search(Node node, String value, List<Node> track) 
    { 
     if (node == null) return false; 

     if (node.data.equals(value)) 
     { 
      track.add(node); 
      return true; 
     } 

     for(Node child : node.children) 
     { 
      if (Search(child, value, track) 
      { 
       track.add(0, node); 
       return true; 
      } 
     } 

     return false; 
    } 

Answer 3

Следующий код отслеживает путь, добавление узлов в список и удалить их, если они не находятся в пути

boolean getPath(Node root,String targetValue,List<Integer> path) 
{ 
    // base case root is null so path not available 
    if(root==null) 
     return false; 
    //add the data to the path 
    path.add(root.getData()); 
    //if the root has data return true,path already saved 
    if(root.getData().equals(targetValue)) 
     return true; 
    //find the value in all the children 
    for(Node child: children){ 
     if(getPath(child,targetValue,path)) 
      return true; 
    } 
    //if this node does not exist in path remove it 
    path.remove(path.size()-1); 
    return false; 
}