java - 获取树中Node的父路径

Question

我使用以下代码来转换平面结构，例如:

test/test2/test3
test/test5/test2
test/test7/test5/test4
test/test7/test5/test9

进入一棵树，例如:

        test
|        |      |
test2   test5   test7
|        |      |
test3   test2   test5
                |        |
                test4    test9

代码:

import java.util.*;
class Tree
{
    class Node
    {
        String data;
        ArrayList<Node> children;

        public Node(String data)
        {
            this.data = data;
            children = new ArrayList<Node>();
        }

        public ArrayList<Node> getChildren()
        {
            return children;
        }

        public Node getChild(String data)
        {
            for(Node n : children)
                if(n.data.equals(data))
                    return n;

            return null;
        }
    }

    private Node root;

    public Tree()
    {
        root = new Node("");
    }

    public boolean isEmpty()
    {
        return root==null;
    }

    public void add(String str)
    {
        Node current = root;
        StringTokenizer s = new StringTokenizer(str, "/");
        while(s.hasMoreElements())
        {
            str = (String)s.nextElement();
            Node child = current.getChild(str);
            if(child==null)
            {
                current.children.add(new Node(str));
                child = current.getChild(str);
            }
            current = child;
        }
    }

    public void get()
    {
        return root;
    }
}

我使用“添加”功能将上面的平坦路径分割为一棵树，它工作得很好，我能够向前导航。不过，我希望能够导航到具有给定路径的节点，并且当我导航到某个节点时，我希望能够将其跟踪到根元素。例如，如果我从 test -> test2 -> test3 导航，我想从根获取路径，如 test/test2/test3。

我是 Trees 新手，这个主题让我有点困惑，非常感谢您的帮助。

编辑:添加了视觉表示。

Answer 1

public class Tree {

    private final Node root = new Node(null, null);

    public boolean isEmpty() {
        return root.children.isEmpty();
    }

    public void add(String path) {
        Node parent = root;

        for (String data : path.split("/")) {
            Node node = parent.getChild(data);

            if (node == null)
                parent.children.add(node = new Node(data, parent));

            parent = node;
        }
    }

    public Node get(String path) {
        Node parent = root;

        for (String data : path.split("/")) {
            Node node = parent.getChild(data);

            if (node == null)
                return null;

            parent = node;
        }

        return parent;
    }

    public static final class Node {

        private final String data;
        private final Node parent;
        private final List<Node> children = new LinkedList<>();

        public Node(String data, Node parent) {
            this.data = data;
            this.parent = parent;
        }

        public List<Node> getChildren() {
            return Collections.unmodifiableList(children);
        }

        public Node getChild(String data) {
            for (Node node : children)
                if (node.data.equals(data))
                    return node;

            return null;
        }

        public String getPath() {
            Deque<String> nodes = new LinkedList<>();
            Node node = this;

            while (node.parent != null) {
                nodes.addFirst(node.data);
                node = node.parent;
            }

            return String.join("/", nodes);
        }

        @Override
        public String toString() {
            return data;
        }
    }

    public static void main(String... args) {
        Tree tree = new Tree();
        tree.add("test/test2/test3");
        tree.add("test/test5/test2");
        tree.add("test/test7/test5/test4");
        tree.add("test/test7/test5/test9");

        Node node = tree.get("test/test7/test5/test9");
        String path = node.getPath();
    }

}