java - 二叉搜索树迭代非键

Question

我有点困惑。我需要打印 BST 中所有不是键的值。因此，由于树不是根据这些值排序的，所以我不能像过去通常使用 BST 那样做。我只需要查看树上的每个节点，将非键值与我输入的值进行比较，并确定是否打印它。

即我需要打印 2.0 以上所有 GPA 的学生目录。由于树是按学生 ID 而不是 GPA 排序的，我如何遍历每个节点并比较 GPA 并打印所有高于 2.0 的节点？

如果您需要查看我的代码，全部内容都在这里，而且非常庞大。

public class StudentBST
{
private static Node root;

static class Node
{
    public int studentID;
    public String lastName;
    public String firstName;
    public String major;
    public double gpa;
    public Node left, right;

    public int minValue()
    {
        if(left == null)
        {
            return studentID;
        }
        else
        {
            return left.minValue();
        }
    }

    public boolean remove(int i, Node node)
    {
        if(i < this.studentID)
        {
            if(left != null)
            {
                return left.remove(i, this);
            }
            else
            {
                return false;
            }
        }
        else if(i > this.studentID)
        {
            if(right != null)
            {
                return right.remove(i, this);
            }
            else
            {
                return false;
            }
        }
        else
        {
            if(left != null && right != null)
            {
                this.studentID = right.minValue();
                right.remove(this.studentID, this);
            }
            else if(node.left == this)
            {
                node.left = (left != null) ? left : right;
            }
            else if(node.right == this)
            {
                node.right = (left != null) ? left : right;
            }
            return true;
        }
    }

    public Node(int i, String l, String f, String m, double g)
    {
    studentID = i;
    lastName = l;
    firstName = f;
    major = m;
    gpa = g;
    left = null;
    right = null;
    }
}
public StudentBST()
{
    root = null;
}
private static void insert(int i, String l, String f, String m, double g)
{
    root = insert(root, i, l, f, m , g);
}
private static Node insert(Node node, int i, String l, String f, String m, double g)
{
    if(node == null)
    {
        node = new Node(i, l, f, m, g);
    }
    else
    {
        if(i <= node.studentID)
        {
            node.left = insert(node.left, i, l, f, m, g);
        }
        else
        {
            node.right = insert(node.right, i, l, f, m, g);
        }
    }
    return(node);
}
public static void printBST()
{
    printBST(root);
    System.out.println();
}
private static void printBST(Node node)
{
    if(node == null)
    {
        return;
    }
    printBST(node.left);
    System.out.println(node.studentID + ", " + node.lastName + ", " + node.firstName
    + ", " + node.major + ", " + node.gpa);
    printBST(node.right);
}
public static boolean remove(int i)
{
    if(root == null)
    {
        return false;
    }
    else
    {
        if(root.studentID == i)
        {
            Node auxRoot = new Node(0, "", "", "", 0);
            auxRoot.left = root;
            boolean result = root.remove(i, auxRoot);
            root = auxRoot.left;
            return result;
        }
        else
        {
            return root.remove(i, null);
        }
    }
}
public static void main(String[] args) 
{
    StudentBST.insert(8, "Costanza", "George", "Napping", 1.60);
    StudentBST.insert(10, "Kramer", "Cosmo", "Chemistry", 3.04);
    StudentBST.insert(5, "Seinfeld", "Jerry", "Theater", 2.05);

    StudentBST.printBST();
    Scanner input = new Scanner(System.in);
    int option = 9;

    while(option != 0)
    {
        System.out.println("1 - Add new student 2 - Delete student 3 - Print All" + 
                " 0 - Exit");
        option = input.nextInt();

        if(option == 1)
        {
            System.out.println("Enter student ID");
            int i = input.nextInt();
            input.nextLine();

            System.out.println("Enter Last Name");
            String l = input.nextLine();

            System.out.println("Enter First Name");
            String f = input.nextLine();

            System.out.println("Enter major");
            String m = input.nextLine();

            System.out.println("Enter GPA");
            Double g = input.nextDouble();

            System.out.println("Inserted student record");
            StudentBST.insert(i, l, f, m, g);
        }
        if(option == 2)
        {
            System.out.println("Enter Student ID to delete");
            int i = input.nextInt();
            boolean b = StudentBST.remove(i);
            if(b)
            {
                System.out.println("Deletion completed");
            }
            else
            {
                System.out.println("Deletion encountered error");
            }
        }
        if(option == 3)
        {
            StudentBST.printBST();
        }
    }
}

Answer 1

我认为您的想法是正确的:只需遍历整棵树并打印出高于某个阈值的 GPA。粗略的实现如下:

public void printGPAs(Node node, double gpa_cutoff) {
    if (node == null) {
        return;
    } 

    if (node.gpa >= gpa_cutoff) {
        System.out.println(node.gpa);
    }

    printGPAs(node.left);
    printGPAs(node.right);
}

如果您想按特定顺序打印它们，最简单的方法是边打印边将它们放入列表中，插入正确的位置以保持您想要的顺序。