如何将AVL Tree中的元组(key，value)添加到Java中的优先级队列？

我是一个java开发新手。我想构建一个优先级队列，其中的元素是我的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);
            
                }
}

下面是我在www.example.com类中定义AVL树节点的方法AVLTree.java：

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

代码有什么问题？我怎么才能修复它？我知道我需要将www.example.com类“连接”AVLTree.java到PriorityQueue_AVL.java类，以便能够在那里使用对象Node，但我不确定如何。此外，优先级队列的语法关闭，我无法查明原因。

我有一些评论要提供，基于OP的原始问题和最近的回复。由于OP似乎没有具体的技术问题，我只是要提供一些评论，希望能推动他们前进。
首先，我尽量不要太在意AVL树和PriorityQueue之间的集成。将此作为最终目标是很好的，但是大多数数据结构的良好实现都应该足够通用，以便可以轻松地修改它们以接受稍微不同的传入数据类型。通常可以使用generics来实现（看起来你已经很熟悉了），但是好的，灵活的类设计也可以走很长的路。所以首先，我会专注于创建一个功能性的AVL树，它只存储，例如，整数，然后是一个功能性的优先级队列，它也只存储整数，然后你可以担心额外类型的额外复杂性，以及一旦基本功能正常工作后它们之间的接口。这是我个人的哲学，这里还有很多其他可行的设计策略。
第二，你说“我试图创建一个优先级队列类，它接受一个 node（一个元组） 作为输入”。我想指出的是，现在，一个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
1.假设您将示例化单个Tuple对象，因此在类定义中使用static是不合适的，也不会起作用

@Override不应评论
1.您的类缺少一个结束语}。
除此之外，代码对我来说编译得很好，所以如果有其他语法错误需要帮助，需要更多的细节。
最后，我想指出的是，AVLTree（在某种程度上也是PriorityQueue）是一种复杂的数据结构。如果你是Java新手（特别是如果你是一般编程新手），并且你做这个练习纯粹是为了学术目的，我建议你从实现一些简单一点的东西开始（想到ArrayList和LinkedList）。但如果不是这样，忽略。
如果你有额外的，具体的问题，我（或其他人）可能很乐意帮助，但没有更多的代码或细节添加到您原来的问题，我认为以上几乎是我所提供的一切。

如何将AVL Tree中的元组(key，value)添加到Java中的优先级队列？

1条答案

相关问题

热门标签

最新问答