如何将AVL树中的元组（键，值）添加到java中的优先级队列中？

Question

我想建立一个优先级队列，其中的元素是我的AVL树的节点。优先级队列应该对具有最高值的节点进行排序，最后对具有最低值的节点进行排序。我尝试创建一个新类来实现它，但我不确定如何以指示优先级队列中的每个元素都是 AVL 树中的节点的方式创建它。

这是我到目前为止的代码：

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class PriorityQueue_AVL {
    
    static class Tuple implements Comparable<Tuple>{
        String key;
        int value;
             
        public Tuple(String key, int value){
            this.key = key;
            this.value = value;
        }
     
        //@Override
        public int compareTo(Tuple node) {
            return this.value - node.value; //if positive, then this.value is larger so it goes first, and vice versa
        }

在上面类中的

compareTo()

方法的正下方，我还尝试创建一个迭代 AVL 树以将每个元素添加到优先级队列的方法，但我不确定是否应该这样做。

node

、

key

、

value

在方法中都用红色下划线表示：

    static void AVLtoPQ(){
        System.out.println();
        // push elements into priority queue PQ
        PriorityQueue<Tuple> PQ = new PriorityQueue<Tuple>();
        if (AVLTree.node != null) {
            inOrderTraversal(node.left);
            PQ.add(new Tuple(key, value));
            inOrderTraversal(node.right);    
        }
    }

这就是我在

AVLTree.java

类中定义 AVL 树节点的方式：

    public class AVLTree<Key extends Comparable<Key>, Value> {
    
        private Node root;  // root of the AVL tree
    
        // A node of the AVL tree
        public class Node {
            private Key key;           // key of the node
            private Value value;       // value of the node
            private Node left, right;  // left and right subtrees of the node
            private int height;        // height of the node
    
            public Node(Key key, Value value) {
                this.key = key;
                this.value = value;
                this.height = 1;
            }
        }

代码有什么问题，如何修复？我知道我需要将

AVLTree.java

类“连接”到

PriorityQueue_AVL.java

类才能使用那里的对象 Node，但我不确定如何操作。另外，优先级队列的语法已关闭，我无法查明原因。

Answer 1

根据OP的原始问题和最近的答复，我有一些评论要提供。由于OP似乎没有具体的技术问题，我只是提供一些评论，希望能推动他们前进。

首先，我会尽量不要太沉迷于 AVL 树和 PriorityQueue 之间的集成。将此作为最终目标很好，但大多数数据结构的良好实现都足够通用，可以轻松修改它们以接受略有不同的传入数据类型。您通常可以使用 generics 来完成此任务（您似乎已经很熟悉），但是良好、灵活的类设计也可以大有帮助。因此，首先，我将专注于创建一个仅存储整数的功能性 AVL 树，然后创建一个也仅存储整数的功能性优先级队列，然后您可以担心其他类型和之间的接口的额外复杂性一旦基本功能发挥作用，他们两个就可以了。但这是我个人的理念，这里还有很多其他可行的设计策略。

其次，你说“我正在尝试创建一个优先级队列类，它将 node（元组） 作为输入”。我想指出的是，现在节点不是元组，它们也没有以任何方式相互关联。在优先级队列上定义一个接受 AVLTree::Node 实例的方法也会很奇怪；这会将两个本质上不相关的数据结构紧密耦合在一起。如果您想将 Node 提取到它自己的公共类，并让它扩展 Tuple 或类似性质的东西，这是一种选择。但您在现实世界中看到的大多数数据结构实现都是独立的，并且将使用原始类型或泛型类型作为其公共方法。

举个例子，使用一些非常粗糙的代码，无法编译，我认为这是一个糟糕的实现：

public class PriorityQueue{
  private LinkedList<Integer> queue;

  // tied too tightly to a different data structure that should be unrelated
  public void addNodeToPQ(Node node){
    this.queue.addLast(node.value);  // this isn't really how you would add a value to a PriorityQueue, it's just for example
  }
}

PriorityQueue pq = new PriorityQueue();
AVLTree avlTree = new AVLTree();
pq.addNodeToPQ(avlTree.get(1));

虽然这个实现更干净且更具可扩展性

public class PriorityQueue{
  private LinkedList<Integer> queue;

  // Uses a very basic type (Integer), rather than relying on another specialized data structure.  This allows multiple consumers to use your PriorityQueue, not just your AVLTree
  public void addValueToPQ(Integer value){
    this.queue.addLast(value); // this isn't really how you would add a value to a PriorityQueue, it's just for example
  }
}

PriorityQueue pq = new PriorityQueue();
AVLTree avlTree = new AVLTree();
pq.addValueToPQ(avlTree.get(1).value);

关于您的

PriorityQueue_AVL

代码中的错误，我可以立即想到我要更改的4件事

1. 没有明显的理由在你的类中导入 HashMap、Map 或 PriorityQueue
2. 大概您将实例化各个 Tuple 对象，因此在类定义中使用

   static

   是不合适的并且不起作用

3. @Override

   不应该评论
4. 您错过了课程结束

   }

   。

除此之外，代码对我来说编译得很好，所以如果您需要帮助解决其他语法错误，则需要更多详细信息。

最后，我确实想指出 AVLTree（某种程度上也是 PriorityQueue）是一个复杂的数据结构。如果您是 Java 新手（尤其是一般编程新手），并且您纯粹出于学术目的而进行此练习，我建议您从实现一些更简单的东西开始（例如 ArrayList 和 LinkedList）。但如果不是这样，请忽略。

如果您有其他具体问题，我（或其他人）可能很乐意提供帮助，但如果没有在您的原始问题中添加更多代码或详细信息，我认为以上内容几乎就是我必须提供的所有内容。