在樹中找到節點的路徑？

我有一個樹類，看起來像：在樹中找到節點的路徑？

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

凡樹根包含指向子節點這點與其他孩子等等等等什麼我有問題是，一旦它找到節點，我需要返回該節點的路徑。

來源

2013-11-27 user2998228

創建一個堆棧 - 顯式或隱式（如遞歸）。該堆棧將包含路徑。 – user2864740

'SearchTreeNode'與'Node'是同一個類？ –

對不起，它是。我改變了它。 – user2998228

如果節點只指向自己的孩子，你需要跟蹤每個路徑的前進的道路。正如評論中提到的那樣，您可以使用自己的堆棧或遞歸進行此操作。例如，您總是可以在每個節點的子節點上返回find（）調用。

如果節點指向兩種方式，你可以很容易地重新跟蹤路徑了，一旦你找到正確的節點。

來源

2013-11-27 02:42:37 Ari

他們只指向他們的孩子。我無法弄清楚如何有效跟蹤當前路徑 – user2998228

通過列表跟蹤路徑，一旦找到節點，退出遞歸和填充路徑一個接一個。

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

來源

2013-11-27 02:54:26

列表中沒有'insert'方法.... – OhadR

下面的代碼跟蹤路徑，將節點添加到列表和刪除他們，如果他們不在路徑

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

來源

2017-02-08 14:46:24 neha

在樹中找到節點的路徑？

回答

相關問題