在树中找到节点的路径? [英] Find path to node in Tree?

问题描述

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

I have a tree class that looks like:

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

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

Where the tree root contains pointers to children nodes which point to other children etc etc. What I'm having problems with is once it finds the node, I need to return the the path to that node.

推荐答案

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

passing a list tracking the path, once find the node, exit the recursion and fill the path one by one.

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

这篇关于在树中找到节点的路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！