AVL Tree Traversal, задачи поиска

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

}

Вывод для обхода следующий:

Traversal: 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.