Поиск пути от узла root к указанному узлу в дереве с помощью рекурсии

Question

Справочная информация: Я впервые использую дерево, мне было поручено создать дерево с использованием королевского семейства, используя файл data.txt

data.txt:

King George VI
King George VI > Princess Margaret
Princess Margaret > David, Viscount Linley
Princess Margaret > Lady Sarah
Lady Sarah > Samuel Chatto
Lady Sarah > Arthur Chatto
David, Viscount Linley > Charles Armstrong-Jones
David, Viscount Linley > Margarita Armstrong-Jones
King George VI > Queen Elizabeth II
Queen Elizabeth II > Charles, Prince of Wales
Charles, Prince of Wales > Prince William of Wales
Prince William of Wales > Prince George of Cambridge
Charles, Prince of Wales > Prince Harry of Wales
Queen Elizabeth II > Anne, Princess Royal
Anne, Princess Royal > Peter Phillips
Peter Phillips > Savannah Phillips
Peter Phillips > Isla Phillips
Anne, Princess Royal > Zara Tindall
Queen Elizabeth II > Andrew, Duke of York
Andrew, Duke of York > Princess Beatrice of York
Andrew, Duke of York > Princess Eugenie of York
Queen Elizabeth II > Edward, Earl of Wessex
Edward, Earl of Wessex > Lady Louise Windsor
Edward, Earl of Wessex > James, Viscount Severn

Фон (Cotd.) : Затем я ищу принцессу Беатриче Йоркскую и нахожу ее соответствующий узел.

    public static void main(String[] args)
    {
        //Define a variable to store the root node
        TNode<String> root = null;

        //TODO: SETUP TREE DATA
        //1. Use Scanner to read the data.txt file
        //2. The first line in data.txt is the root node
        //3. For each line in data.txt in the format A > B
        //      - *find* the A node
        //      - add B as a child of A
        try
        {
            Scanner s = new Scanner(new File("data.txt"));
            while(s.hasNextLine())
            {
                String[] split = null;
                if(!s.nextLine().contains(">"))
                {
                    root = new TNode<String>(s.nextLine());
                }else{
                     split = s.nextLine().split(" > ");
                }
                find(root,split[0]).setParent(new TNode(split[3]));
            }
            s.close();
        }catch(Exception e){
            e.printStackTrace();
        }
        //TODO: test printPath method
        TNode<String> child = find(root, "Princess Beatrice of York");
        String path = getPath( child );
        System.out.println(path);

    }

метод поиска:

    /**
     *  @return node if its data matches name, or return a child node with data that matches name
     */
    public static TNode<String> find(TNode<String> node, String name)
    {
        //use recursion to check this node and all of its children to see if their data matches the specified name
        if(node.getData().equals(name))
        {
            return node;
        }
        for(int i = 0; i < node.getChildren().size(); i++)
        {
            return find(node.getChildren().get(i),name);
        }
        return null;
    }

Цель: вернуть строку, содержащую путь от узла root к указанному узлу, разделенному '- > 'начиная с дочернего узла

Моя попытка:

    public static String getPath(TNode<String> node)
    {
        //use recursion to concatenate the getPath of this node's parent with this node's data
        if(!node.getParent().equals(null))
            return getPath(node.getParent()) + " -> " + node.getData(); 
        return getPath(node.getParent());
    }

Вопросы:

1.

возможно ли это вообще во-первых

2.

как я могу объединить строку, если нет строки, которую я мог бы объединить.

3.

Какими способами можно помочь мне разобраться в логике c рекурсивных проблем

Answer 1

Это абсолютно возможно. Просто взглянув на него, вы можете проследить от Princess Beatrice of York до King George VI.

. Чтобы создать строку семейной линии (если вы этого хотите), вы можете сохранить каждого человека в TNode и объединить имена с > между ними, начиная с root.

Чтобы научиться думать о рекурсивных алгоритмах, начните с чего-то более простого, например длины строки или вычисления факториала числа.