AVL树遍历、搜索问题

Question

我在 AVL 树实现中遇到了一些问题。所有旋转和添加的代码似乎都是正确的，我试运行该程序以彻底检查它在逻辑上运行是否正确。我的树遍历（按顺序）似乎遇到了问题，因为它只输出假定的 100 中的几个整数。而且，无论我输入什么，搜索总是失败。我似乎无法理解发生了什么，但我怀疑它与一些空指针有关。下面是AVL树的代码，我想知道AddNode方法或旋转方法中是否有任何错误的代码，但它们似乎没问题。这些类是Node类，AVL类和AVL树类，这是主类。

节点类

private int data;
private Node left;
private Node right;     
private int height;

public Node(int m) {
    data = m;        
    left = null;
    right = null;
    height = 0;
}

public void setToleft(Node newleft) {
    left = newleft;
}

public Node getleftNode() {
    return left;
}

public void setToright(Node newright) {
    right = newright;
}

public Node getrightNode() {
    return right;
}

public int getData() {
    return data;
}

public int getHeight(){
    return height;
}

public void setHeight(int height){
    this.height = height;
}

AVL 类

public Node root;

public AVL(int root) {
    this.root = new Node(root); // since root presently has no left or right children, height is currently 0
}

public int Height(Node n) {

    if (n == null) { //basis step                 
        return -1;
    } else { //add one for every path 
        if (n.getleftNode() == null && n.getrightNode() == null) {
            return 0;
        }
        return 1 + Math.max(Height(n.getleftNode()), Height(n.getrightNode()));
    }
}

public void add(int data) {
    addNode(data, root);
    root.setHeight(Math.max(Height(root.getleftNode()), Height(root.getrightNode())) + 1);
}

public void addNode(int data, Node n) {

    if (data < n.getData()) {
        if (n.getleftNode() == null) {
            n.setToleft(new Node(data));
        } else {
            addNode(data, n.getleftNode());
        }

        n.setHeight(Math.max(Height(n.getleftNode()), Height(n.getrightNode())) + 1);

        if ((Height(n.getleftNode()) + 1) - (Height(n.getrightNode()) + 1) == Math.abs(2)) {
            if (data < n.getleftNode().getData()) {
                n = LLRotation(n);
            } else {
                n = LRRotation(n);
            }
        }
    } else if (data >= n.getData()) {  //>= also caters for duplicates and inserts them infront of same value
        if (n.getrightNode() == null) {
            n.setToright(new Node(data));
        } else {
            addNode(data, n.getrightNode());
        }

        n.setHeight(Math.max(Height(n.getleftNode()), Height(n.getrightNode())) + 1);

        if ((Height(n.getrightNode()) + 1) - (Height(n.getleftNode()) + 1) == Math.abs(2)) {
            if (data >= n.getrightNode().getData()) {
                n = RRRotation(n);
            } else {
                n = RLRotation(n);
            }
        }
    }
}

public Node LLRotation(Node n) {      //single

    Node n1 = n.getleftNode();
    n.setToleft(n1.getrightNode());
    n1.setToright(n);
    n.setHeight(Math.max(Height(n.getleftNode()), Height(n.getrightNode())) + 1);
    n1.setHeight(Math.max(Height(n1.getleftNode()), Height(n)) + 1);
    //compares heights of left and right subtrees and gets max
    //the above source code is of course vital since the node height must be resetted after rotations
    //adding 1 at the end of the last two code lines is important since 
    //initially the height is only calculated from subtrees onwards
    //same for single right rotation below
    return n1;
}

public Node RRRotation(Node n) {   //single

    Node n1 = n.getrightNode();
    n.setToright(n1.getleftNode());
    n1.setToleft(n);
    n.setHeight(Math.max(Height(n.getleftNode()), Height(n.getrightNode())) + 1);
    n1.setHeight(Math.max(Height(n1.getrightNode()), Height(n)) + 1);

    return n1;
}

public Node LRRotation(Node n) {   //double

    n.setToleft(RRRotation(n.getleftNode()));
    return LLRotation(n);       
}

public Node RLRotation(Node n) {   //double

    n.setToright(LLRotation(n.getrightNode()));
    return RRRotation(n);         
}

public void inOrderTraversal(Node n) {

    if (n != null) {
        inOrderTraversal(n.getleftNode()); //recursive call to the left subtree
        System.out.println(n.getData()); //line which makes the actual node to display its data
        inOrderTraversal(n.getrightNode()); //recursive call to the right subtree
    }

}

public void traverse() {
    inOrderTraversal(root);   // can be called in main class to automatically traverse tree from its root
}

public int search(int x) {
    try {
        if (x == root.getData()) { //basis step
            System.out.println("Item found!");
            return x;
        }
        if (x < root.getData()) {
            root = root.getleftNode();
            return search(x);//recursive call
        } else {
            root = root.getrightNode();
            return search(x);//recursive call
        }
    } catch (NullPointerException e) {
        System.out.println ("Search failed!");
        return 0;
    }
}

主类

public static void main(String[] args) throws IOException {

    Scanner s = new Scanner(System.in);

    AVL tree = null;

    int choice = 0;

    System.out.println("AVL TREE");

    System.out.println("\n Choose an option from the menu: ");
    System.out.println("\n\t 1.) Create file of 100 integers");
    System.out.println("\n\t 2.) Create the tree");
    System.out.println("\n\t 3.) In-Order traverse and show tree");
    System.out.println("\n\t 4.) Search for integer");
    System.out.println("\n\t 5.) Quit");

    while (choice != 5) {

        System.out.print("\nChoice: ");
        choice = s.nextInt();

        switch (choice) {

            case 1:
                createFile();
                break;

            case 2:
                try {
                    FileReader readto = new FileReader("Integers.txt");
                    BufferedReader br = new BufferedReader(readto);

                    String line = br.readLine(); //reads text at start of file                        
                    line = br.readLine(); // skipping empty lines                      
                    line = br.readLine();
                    line = br.readLine();

                    int root = Integer.parseInt(line);   //extracts first integer from the line
                    System.out.println("Root: " + root);

                    tree = new AVL(root);                        

                    int x = 0;
                    while (x != 99) {
                        try {
                            line = br.readLine();
                            int next = Integer.parseInt(line);
                            tree.add(next);
                            System.out.println(next);
                            x++;
                        } catch (NumberFormatException e) {
                        };
                    }
                    System.out.println("Tree successfully populated!");
                } catch (FileNotFoundException e) {
                    System.out.println("ERROR: File not found!");
                }
                break;

            case 3:
                System.out.println("In-Order traversel executed. The now balanced tree shall now be printed in");
                System.out.println("ascending order and also the left and right children of each node shall be printed.\n");

                System.out.println("Traversal: ");

                tree.traverse();
                break;

            case 4: 
                System.out.print("Please enter the integer to be searched: ");
                int x = s.nextInt();

                System.out.println(tree.search(x));
                break;

            case 5:
                System.exit(0);
                break;

            default:
                System.out.println("ERROR: Choice out of bounds!");
        }

    }
}

static void createFile() throws IOException {

    Random r = new Random();

    File intfile = new File("Integers.txt");
    FileWriter writeto = new FileWriter("Integers.txt");
    BufferedWriter bw = new BufferedWriter(writeto);
    if (!(intfile.exists())) {
        System.out.println("ERROR: File not found!");
    } else {

        bw.write("The following integers are randomly generated");
        bw.newLine();
        bw.write("and will be used to construct the AVL tree:");
        bw.newLine();
        bw.newLine();

        int x;

        System.out.println("The following random numbers shall be used to build the AVL tree: \n");

        for (int i = 0; i < 100; i++) {
            x = r.nextInt(100) + 1;
            bw.write(String.valueOf(x));
            bw.newLine();
            System.out.println(x);
        }
        bw.close();
    }

}

遍历的输出如下：

遍历： 44 53 54 54 77

假设输入了 100 个整数，其中有这些。但遍历的输出仅此而已。

搜索的输出如下： 选择：4 请输入要查找的整数：44 物品找到了！ 44

选择：4 请输入要查找的整数：100 搜索失败！ 0

100 和 44 都是添加到树中的整数，但是找到了 44 而没有找到 100.. 我不明白..

任何人都可以指导我解决方案..？

提前致谢 ：）

Answer 1

好吧，首先是显而易见的事情......在您的 search 方法中，您滥用了 root 变量，该变量保存树的根，将其设置为新值作为您的搜索继续进行。因此，在第一次搜索之后，root 指向搜索中遍历的最后一个节点，而不再指向树的根节点。从那时起，所有后续搜索都不太可能找到任何东西。

由于您的搜索是递归的，请尝试将要搜索的节点作为参数传递：（

int search(Node node, int key) {

    if (node == null) {

         return 0;  // missing from tree

    } else if (key < node.getData()) {

         return search(node.getLeft(), key);

    } else if (key > node.getData()) {

         return search(node.getRight(), key);

    } else {

         return node.getData();  // found it
    }
}

已编辑以解决注释）您可能必须像使用 add/addNode 方法对使用公开可用的包装器和内部实现：

public int search(int key)  {
    return searchNode(root, key);
}

private int searchNode(Node node, int key) {
    // Perform the recursive search, as above
}

还有与您的 add/addNode 相关的其他问题代码>方法。也许我只是忽略了它，但是如果旋转需要的话，你就没有地方调整树的根节点。实际上，这会导致您的树失去平衡，随着时间的推移失去 AVL 属性。