Как рекурсивно найти самое длинное слово в префиксном дереве? - PullRequest
Новая
       67

Как рекурсивно найти самое длинное слово в префиксном дереве?

0 голосов
/ 10 июля 2020

У меня следующая структура данных: Это дерево хранит только символы в нижнем регистре.

enter image description here

I'm trying to build a method that finds the longest word in the tree recursively. I have difficulty to build this method that checks each branch of the nodes recursively.

Here the given classes I'm using, showing only the relevant methods:

public class Tree {

    private final Node root;

    public Tree() {
        root = new Node('0');
    }

 private String getWordOfBranch(final Node[] nodes, final int i) {

        if (nodes[i] == null) {
            return "";
        }

        if (nodes[i].isLeaf()) {
            return String.valueOf(nodes[i].getValue());
        }

        return nodes[i].getValue() + getWordOfBranch(nodes[i].children, i);
    }


public class Node {

    private final char value;
    protected Node[] children;

    public Node(final char value) {
        this.value = value;
        children = new Node[26];
    }

  public boolean isLeaf() {
        for (final Node child : children) {
            if (child != null) {
                return false;
            }
        }
        return true;
    }

    public char getValue() {
        return value;
    }

Ответы [ 2 ]

0 голосов
/ 11 июля 2020

Я внес некоторые изменения в ваш код. Сначала класс Node. 

import java.util.ArrayList;
import java.util.List;

public class Node {
    private final char  value;
    protected List<Node> children;

    public Node(char letter) {
        value = letter;
        children = new ArrayList<>();
    }

    private static boolean isValidValue(Node node) {
        boolean isValid = false;
        if (node != null) {
            char ch = node.getValue();
            isValid = 'a' <= ch  &&  ch <= 'z';
        }
        return isValid;
    }

    public boolean addChild(Node child) {
        boolean added = false;
        if (child != null) {
            if (isValidValue(child)) {
                boolean found = false;
                for (Node kid : children) {
                    found = kid != null  &&  kid.getValue() == child.getValue();
                    if (found) {
                        break;
                    }
                }
                if (!found) {
                    added = children.add(child);
                }
            }
        }
        return added;
    }

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

    public char getValue() {
        return value;
    }
}

Я использовал List для дочерних элементов, а не массив, потому что массив имеет фиксированный размер, а List - нет.

Теперь класс Tree. Обратите внимание, что я добавил в класс метод main() только для тестирования. Метод main() создает древовидную структуру на изображении в вашем вопросе.

Древовидная структура данных имеет уровни и листья. Лист - это узел в дереве, у которого нет дочерних узлов. Следовательно, каждый лист в вашем дереве - это последняя буква слова. Листья на самом высоком уровне представляют собой самые длинные слова. (Обратите внимание, что уровень узла root в дереве равен нулю.) 

import java.util.ArrayList;
import java.util.List;

public class Tree {
    private int  longest;
    private List<String>  words;
    private Node  root = new Node('\u0000');

    public List<String> getWords() {
        return words;
    }

    public Node getRoot() {
        return root;
    }

    public void visit() {
        visit(root, 0, new StringBuilder());
    }

    public void visit(Node node, int level, StringBuilder word) {
        if (node != null) {
            word.append(node.getValue());
            List<Node> children = node.getChildren();
            if (children.size() == 0) {
                if (level > longest) {
                    longest = level;
                    words = new ArrayList<>();
                }
                if (level == longest) {
                    words.add(word.toString());
                }
            }
            else {
                for (Node child : children) {
                    word.delete(level, word.length());
                    visit(child, level + 1, word);
                }
            }
        }
    }

    /**
     * For testing only.
     */
    public static void main(String[] args) {
        Tree tree = new Tree();
        Node root = tree.getRoot();
        Node j = new Node('j');
        root.addChild(j);
        Node r = new Node('r');
        root.addChild(r);
        Node a = new Node('a');
        j.addChild(a);
        Node v = new Node('v');
        a.addChild(v);
        Node a2 = new Node('a');
        v.addChild(a2);
        Node a3 = new Node('a');
        r.addChild(a3);
        Node o = new Node('o');
        r.addChild(o);
        Node d = new Node('d');
        a3.addChild(d);
        Node n = new Node('n');
        a3.addChild(n);
        Node d2 = new Node('d');
        n.addChild(d2);
        Node u = new Node('u');
        a3.addChild(u);
        Node m = new Node('m');
        u.addChild(m);
        Node s = new Node('s');
        o.addChild(s);
        Node e = new Node('e');
        s.addChild(e);
        tree.visit();
        System.out.println(tree.getWords());
    }
}

Метод visit(Node, int, StringBuilder) - это рекурсивный метод. Он проходит каждый путь в дереве и добавляет символы в каждом узле к StringBuilder. Следовательно, StringBuilder содержит слово, полученное путем прохождения единственного пути в дереве - от root до листа.

Я также отслеживаю уровень узла, так как самый высокий уровень означает самое длинное слово.

Наконец, я сохраняю все самые длинные слова в другом List.

Выполнение приведенного выше кода дает следующий результат: 

[java, rand, raum, rose]
0 голосов
/ 10 июля 2020

Ну, в этом случае вы берете только слово, начинающееся с определенной c позиции i. Вам следует перебрать всех детей в цикле и найти самое длинное слово из всех детей. Кроме того, ваш класс узла не должен иметь установленное количество дочерних элементов, а вместо этого должен иметь список дочерних элементов с динамическим размером, используя что-то вроде ArrayList для хранения дочерних элементов, так как каждый узел не должен иметь заданный c детей. 

    public class Node {

        private final char value;
        protected ArrayList<Node> children;

        public Node(final char value) {
            this.value = value;
            children = new ArrayList<Node>();
        }

        public boolean isLeaf() {
            for (final Node child : children) {
                if (child != null) {
                    return false;
                }
            }
            return true;
        }

        public char getValue() {
            return value;
        }

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

    public String getLargestWord(Node root) {
        if (root.isLeaf()) {
            return String.valueOf(root.getValue());
        }

        else {
            String longest = "";
            for (Node child : root.getChildren()) {
                String longWordInChild = getLongestWord(child);
                if (longWordInChild.length() > longest.length()) {
                    longest = longWordInChild;
                }
            }

            return root.getValue() + longest;
        }
    }
...