java - 将一个节点类型字符串与另一个节点类型字符串进行比较的二叉搜索树

Question

我正在研究二叉搜索树数据结构，在尝试比较两个字符串节点时遇到问题。这是我的代码，在第 18 行，我想比较根节点和另一个字符串节点。

nodeToAdd.word < node.word //this is how i want to compare the nodes

我知道你不能使用<或>比较字符串时，您将使用 compareTo()或equals() 。在这种情况下，当比较节点时，我将如何比较两个节点以查看哪个节点按字母顺序更高或更低？

public class binarytree implements WordStore {

    Node root;

    public void add(String word) {
        Node nodeToAdd = new Node(word);

        if (root == null) {
            // if there's no root, then the node becomes root

            root = nodeToAdd;
        }
        traverseAdd(root, nodeToAdd);

    }
    private void traverseAdd(Node node, Node nodeToAdd) {

        if (nodeToAdd.word < node.word)) {
            if (node.leftChild == null) {
                node.leftChild = nodeToAdd;
            } else {
                traverseAdd(node.leftChild, nodeToAdd);
            }
     //more code not relevant....
}

Answer 1

要比较两个节点，请定义一个Comparator:

Comparator<Node> nodeComparer = Comparator.comparing(node -> node.word);

现在要比较两个节点，您可以使用:

nodeCompare.compare(node1, node2);

不要在类上实现Comparable，除非该类有一个在大多数情况下都合理的自然排序(排序、查找最小、最大等)。我不认为这对于节点来说是正确的。我可以想象想要按树中的深度或后代的数量进行排序，或找到具有最长字符串或其他标准的节点。最好使用适合您需要的自定义Comparator。

另请注意，如果您实现Comparable，您可能还应该定义equals和hashCode，因为强烈建议自然顺序保持一致等于(参见 Comparable )。

查看this question的答案有关自然排序以及何时使用它的更多信息。