首页 文章

在Tree中查找节点的路径？

提问于
浏览 次
4

我有一个树类，看起来像：

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

树根包含指向其他子节点的子节点的指针等等 . 我遇到的问题是，一旦找到节点，我需要返回该节点的路径 .

java tree

3 回答

  • 0

    传递跟踪路径的列表，一旦找到节点，退出递归并逐个填充路径 .

    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;
    }
    回复于
  • 0

    如果节点仅指向其子节点，则需要在向下的路径上跟踪每条路径 . 正如评论中所提到的，您可以使用自己的堆栈或递归来完成此操作 . 例如，您始终可以对每个节点的子节点返回find（）调用 .

    如果节点指向两个方向，则一旦找到正确的节点，就可以轻松地重新跟踪路径 .

    回复于
  • 9

    以下代码跟踪路径，将节点添加到列表中，如果它们不在路径中，则将其删除

    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;
}
    回复于

相关问题