java - 打印 AVL 树的顶部“m”个元素

Question

我必须编写一个程序来读取 n 个学生的组和分数，并使用 AVL 树计算所有组的平均值。然后我应该按降序打印具有最高平均值的前“m”组。

输入规范：两个整数：学生人数（n）和要列出的前 m 个组的数量。然后在接下来的 n 行中，你会得到两个信息：学生所在的组和这个学生的分数。

输出规范：按降序显示前 m 个组。

样本输入：6 2 CEN1 20 CEN1 28 CEN2 10 ECE1 21 CEN2 10 ECE1 19

样本输出：CEN1 ECE1

解释：CEN1 的平均值是 24，ECE1 是 20，CEN2 是 10。因此，前两组是 CEN1 和 ECE1。

这是我到目前为止所做的，我的程序正确打印了所有 3 个组及其平均值，但我不知道如何根据平均值而不是组名按降序打印它们中的前“m”。

package exercise;

import java.util.Scanner;

class AVLNode {

    AVLNode left, right; //pointers to left and right nodes
    int height; //height of the tree
    int cnt; //number of occurrences of a group
    String group; 
    int points;

    public AVLNode(String group, int points) {
        left = null;
        right = null;
        height = 0;
        cnt = 1;
        this.group = group;
        this.points = points;
    }
}

class AVLTree {

    private AVLNode root; //root of the tree
    
    /* No-arg constructor */
    public AVLTree() {
        root = null;
    }
    
    /* Method to get height of node */
    private int height(AVLNode t) {
        return t == null ? -1 : t.height;
    }

    /* Method to max of left/right node */
    private int max(int lhs, int rhs) {
        return lhs > rhs ? lhs : rhs;
    }

    /* Method to insert data */
    public void insert(String group, int points) {
        root = insert(group, points, root);
    }
    /* Helper method to insert data recursively */
    private AVLNode insert(String group, int points, AVLNode t) {
        
        if (t == null) 
            t = new AVLNode(group, points);
    
        else if(group.compareTo(t.group) < 0) //if given group is < than root's group
        {
            t.left = insert(group, points, t.left); //insert to the left
            if (height(t.left) - height(t.right) == 2)
                if(group.compareTo(t.group) < 0)
                    t = rotateWithLeftChild(t); // left - left tree
                else
                    t = doubleWithLeftChild(t); // left-right tree
        }

        else if(group.compareTo(t.group) > 0) //if given group is > than root's group
        {
            t.right = insert(group, points, t.right); //insert to the right
            if (height(t.right) - height(t.left) == 2)
                
                if (group.compareTo(t.group) > 0)
                    t = rotateWithRightChild(t);  // right -right tree
                else
                    t = doubleWithRightChild(t);  // right - left tree
        }
        else {
            t.cnt++; //if that group already exists, don't add it to the tree, increment its counter and add the points
            t.points += points;
        }

        t.height = max(height(t.left), height(t.right)) + 1;
        return t;

    }

    
    /* Rotate binary tree node with left child */
    private AVLNode rotateWithLeftChild(AVLNode k2) {

        AVLNode k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        k2.height = max(height(k2.left), height(k2.right)) + 1;
        k1.height = max(height(k1.left), k2.height) + 1;
        return k1;

    }

    /* Rotate binary tree node with right child */
    private AVLNode rotateWithRightChild(AVLNode k1) {
 
        AVLNode k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        k1.height = max(height(k1.left), height(k1.right)) + 1;
        k2.height = max(height(k2.right), k1.height) + 1;

        return k2;

    }

    /**
     * Double rotate binary tree node: first left child
     * with its right child; then node k3 with new left child
     **/
    private AVLNode doubleWithLeftChild(AVLNode k3) {
        
        k3.left = rotateWithRightChild(k3.left);
        return rotateWithLeftChild(k3);
    }

    /**
     * Double rotate binary tree node: first right child
     * with its left child; then node k1 with new right child
     **/
    private AVLNode doubleWithRightChild(AVLNode k1) {

        k1.right = rotateWithLeftChild(k1.right);
        return rotateWithRightChild(k1);

    }

    /* Method to print elements of the tree */
    public  void print() {
        print(root);
    }
    
    /* Helper method to print elements of the tree recursively */
    private  void print(AVLNode r) {
        if (r.left != null)
            print(r.left);
        System.out.println(r.group + " " + (double)r.points / r.cnt);
        if (r.right != null)
            print(r.right);
    }
    
}
    
public class AVLSolution {

    public static void main(String[] args) { //main method
        
        Scanner input = new Scanner(System.in); //Scanner object to get input from the user
        AVLTree avlt = new AVLTree(); //construct the tree
        
        int n = input.nextInt(), m = input.nextInt(); 
        
        for (int i = 0; i < n; i++) { //iterate through students
            
            String group = input.next();
            int points = input.nextInt();
            
            avlt.insert(group, points);

        }
        
            avlt.print();
        
    }

}

标签： javasortingtreebinary-search-treeavl-tree