0

我有以下数据结构： 此树仅存储小写字符。

在此处输入图像描述

我正在尝试构建一种递归查找树中最长单词的方法。我很难构建这种递归检查每个节点分支的方法。

这是我正在使用的给定类，仅显示相关方法：

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

2 回答 2

0

我对您的代码进行了一些更改。
先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孩子，而不是数组，因为数组具有固定大小而 aList没有。

现在Tree上课。请注意，我main()在类中添加了一个方法只是为了测试目的。该main()方法在您的问题的图像中创建树结构。

树数据结构有层次，也有叶子。叶是树中没有子节点的节点。因此，树上的每一片叶子都是单词的最后一个字母。最高层的叶子代表最长的单词。（请注意，树中根节点的级别为零。）

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包含通过遍历树中的单个路径（从根到叶）获得的单词。

我还跟踪节点级别，因为最高级别意味着最长的单词。

最后，我将所有最长的单词存储在另一个List.

运行上面的代码会产生以下输出：

[java, rand, raum, rose]
于 2020-07-11T17:59:41.387 回答
0

好吧，在这种情况下，您只使用从特定位置开始的单词i。你应该做的是遍历所有的孩子并从所有孩子中找出最长的单词。此外，您的节点类不应该有一定数量的子节点，而是一个动态大小的子节点列表，使用类似 an 的东西ArrayList来存储子节点，因为每个节点不必有一组特定的子节点。

    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;
        }
    }
于 2020-07-09T23:38:55.373 回答