Помощь в домашнем задании: массив странный

Я работаю над назначением двоичного дерева поиска, и я тестировал то, что я считал готовым продуктом, когда я увидел, что когда я добавил число в дерево, а затем попытался проверить его предшественника / преемника (поместив его в массив используя обход по порядку, а затем проверяя индекс до / после него) это просто ... не сработало. Каждый раз, когда я пытаюсь проверить предшественника / преемника значения, которое я только что поместил в середину дерева, он выдает исключение ArrayIndexOutOfBoundsException. Важное замечание: простая печать с использованием inordertraverse (называемого в коде printInOrder) отлично работает.

Поскольку печать неупорядоченного обхода работает, я могу предположить, что проблема не в моем дереве. Другое дело - массив, верно? Я упускаю что-то очевидное?

Вот код!

public class BST implements BSTInterface
{
//Variables/Fields
    private BNode root;

//Constructors
    public BST(int data)
    {
        root = new BNode(data);
    }

//Public Methods
    public boolean add(int data)
    {
        if(!contains(data))
        {
            root = addEntry(root, data);
            return true;
        }
        else
            return false;
    }

    public boolean contains(int data)
    {
        return containsNode(root, data);
    }

    public boolean remove(int data)
    {
        if(contains(data))
        {
            root = deleteNode(root, data);
            return true;
        }
        else
            return false;
    }

    public int[] toArray()
    {
        int[] output = new int[root.numNodes()];
        inorderTraverse(output, 0, root);
        return output;
    }

    public void printInOrder()
    {
        printIn(root);
    }

    public void printPreOrder()
    {
        printPre(root);
    }

    public void printPostOrder()
    {
        printPost(root);
    }


//Private methods/classes
    private class BNode
    {
        private int data;
        private BNode leftChild;
        private BNode rightChild;

        public BNode(int data)
        {
            this.data = data;
            leftChild = null;
            rightChild = null;
        }

        public int getData()
        {
            return data;
        }

        public void setData(int newData)
        {
            data = newData;
        }

        public BNode getLeftChild()
        {
            return leftChild;
        }

        public BNode getRightChild()
        {
            return rightChild;
        }

        public void setRightChild(BNode node)
        {
            rightChild = node;
        }

        public void setLeftChild(BNode node)
        {
            leftChild = node;
        }

        public int numNodes()
        {
            int leftNum = 0;
            int rightNum = 0;

            if(leftChild != null)
                leftNum = leftChild.numNodes();
            if(rightChild != null)
                rightNum = rightChild.numNodes();

            return 1+leftNum+rightNum;
        }


    }

    private BNode addEntry(BNode current, int data)
    {
        if(current == null)
            return new BNode(data);
        if(data < current.getData())
            current.setLeftChild(addEntry(current.getLeftChild(), data));
        else if(data > current.getData())
            current.setRightChild(addEntry(current.getRightChild(), data));
        return current;
    }

    private boolean containsNode(BNode current, int entry)
    {
        if(current == null)
            return false;
        if(entry == current.getData())
            return true;
        if(entry < current.getData())
            return containsNode(current.getLeftChild(), entry);
        else
            return containsNode(current.getRightChild(), entry);

    }

    private BNode deleteNode(BNode current, int data)
    {
        if(current == null)
            return null;
        if(data == current.getData())
        {
            if(current.getLeftChild() == null && current.getRightChild() == null) //No children
                return null;
            if(current.getRightChild() == null) //Only right child
                return current.getLeftChild();
            if(current.getLeftChild() == null) //Only left child
                return current.getRightChild();
            int smallestChild = findSmallest(current.getRightChild());
            current.setData(smallestChild);
            current.setRightChild(deleteNode(current.getRightChild(), smallestChild));
            return current;
        }
        if(data < current.getData())
        {
            current.setLeftChild(deleteNode(current.getLeftChild(), data));
            return current;
        }
        else
            current.setRightChild(deleteNode(current.getRightChild(), data));
            return current;

    }

    private int findSmallest(BNode root)
    {
        return root.getLeftChild() == null ? root.getData() : findSmallest(root.getLeftChild());
    }

    private void inorderTraverse(int[] array, int count, BNode node)
    {
        if(node != null)
        {
            inorderTraverse(array, count, node.getLeftChild());
            array[count] = node.getData();
            count++;
            inorderTraverse(array, count, node.getRightChild());
        }
    }

    private void printIn(BNode node)
    {
        if(node != null)
        {
            printIn(node.getLeftChild());
            System.out.print(node.getData() + " ");
            printIn(node.getRightChild());
        }
    }

    private void printPre(BNode node)
    {
        if(node != null)
        {
            System.out.print(node.getData() + " ");
            printPre(node.getLeftChild());
            printPre(node.getRightChild());
        }
    }

    private void printPost(BNode node)
    {
        if(node != null)
        {
            printPost(node.getLeftChild());
            printPost(node.getRightChild());
            System.out.print(node.getData() + " ");
        }
    }
}

вместе с программой драйвера:

import java.util.Scanner;
public class BSTDemoReel
{
    public static void main(String[] args)
    {
        System.out.println("This search tree only handles integers! Thanks in advance!\n\n");
        Scanner keyboard = new Scanner(System.in);

        //Variables
        String input;
        String choice = "";
        int num;
        int index;
        boolean found;

        //Starting
        System.out.println("Please enter the initial sequence of values:\n");
        input = keyboard.nextLine();
        String[] splitInput = input.split(" ");
        int[] intInputArray = new int[splitInput.length];
        for(int count = 0; count < splitInput.length; count++)
        {
            intInputArray[count] = Integer.parseInt(splitInput[count]);
        }

        BST searchTree = new BST(intInputArray[0]);
        for(int count = 1; count < intInputArray.length; count++)
        {
            searchTree.add(intInputArray[count]);
        }

        System.out.print("Pre-order: ");
        searchTree.printPreOrder();
        System.out.println();

        System.out.print("In-order: ");
        searchTree.printInOrder();
        System.out.println();

        System.out.print("Post-order: ");
        searchTree.printPostOrder();
        System.out.println();

        //Menu
        while(!choice.equals("E"))
        {
            System.out.print("Command? ");
            choice = keyboard.next();
            choice = choice.toUpperCase();
            switch(choice)
            {
            case "I": num = keyboard.nextInt();
                    if(searchTree.contains(num))
                        System.out.println(num + " already exists. Please try again.");
                    else
                    {
                        searchTree.add(num);
                        System.out.print("In-order: ");
                        searchTree.printInOrder();
                        System.out.println();
                    }
                    break;
            case "D": num = keyboard.nextInt();
                    if(!searchTree.contains(num))
                        System.out.println(num + " does not exist. Please try again.");
                    else
                    {
                        searchTree.remove(num);
                        System.out.print("In-order: ");
                        searchTree.printInOrder();
                        System.out.println();
                    }
                    break;
            case "P": num = keyboard.nextInt();
                    if(searchTree.contains(num))
                    {
                        int[] array = searchTree.toArray();
                        index = 0;
                        found = false;
                        while(!found)
                        {
                            if(num == array[index])
                                found = true;
                            else
                                index++;
                        }
                        if(index != 0)
                            System.out.println(array[index-1]);
                        else
                            System.out.println("That was the first one!");
                    }
                    else
                        System.out.println(num + " does not exist! Please try again!");
                    break;
            case "S": num = keyboard.nextInt();
                   if(searchTree.contains(num))
                    {
                        int[] array = searchTree.toArray();
                        index = 0;
                        found = false;
                        while(!found)
                        {
                            if(num == array[index])
                                found = true;
                            else
                                index++;
                        }
                        if(index != array.length-1)
                            System.out.println(array[index+1]);
                        else
                            System.out.println("That was the last one!");
                    }
                    else
                        System.out.println(num + " does not exist! Please try again!");
                    break;
            case "E": System.out.println("Was a tricky one! Thanks for playing ;P");
                    break;
            case "H": System.out.println("I  Insert a value\n" +
                                         "D  Delete a value\n" +
                                         "P  Find predecessor\n" +
                                         "S  Find successor\n" +
                                         "E  Exit the program\n" +
                                         "H  Display this message");
                    break;

            default: System.out.println("Invalid command. Type H for help.");
                    break;
            }
        }
        keyboard.close();
    }
}
0
0
59
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Если вы добавите пару строк кода для распечатки массива, возвращаемого searchTree.toArray(), перед тем, как войти в цикл while, который исследует массив, чтобы найти значение, указанное с помощью команд P или S, вы увидите причину проблемы. Массив заполнен неправильно. Желаемое значение может отсутствовать в массиве, а это означает, что found никогда не станет True, и цикл while будет продолжать увеличивать index до тех пор, пока он не превысит размер массива и не вызовет исключение, которое вы видите.

Поскольку предполагается, что массив заполняется inorderTraverse(), это говорит о том, что эта функция неправильно выполняет свою работу. Причина неправильного поведения заключается в том, что его внутренние рекурсивные вызовы к самому себе не изменяют значение переменной count для вызывающего. count - это простая переменная int, поэтому оператор count++ внутри рекурсивного вызова не влияет на значение count в вызывающей функции.

Лучше всего либо изменить inorderTraverse(), чтобы он возвращал индекс элемента массива, который должен быть заполнен следующим, либо изменить count на объект, содержащий член int, обновленное значение которого будет видно вызывающему после того, как оно было выполнено. увеличивается внутри рекурсивно вызываемой функции.

Поскольку это задание, я не буду показывать исправленную версию программы. Изменение небольшое, поэтому, учитывая то, что вы сделали до сих пор, я ожидаю, что у вас не будет особых проблем с его работой.

Кстати, в вашей программе отсутствуют реализации printIn(), printPre() и printPost(). Их нетрудно написать, но это дополнительное препятствие для любого, кто мог бы заинтересоваться в том, чтобы помочь вам решить эту проблему. Это может быть, по крайней мере, частью причины, по которой никто еще не дал ответа. Чем проще вы сделаете так, чтобы люди воспроизвели проблему, тем больше вероятность, что вы получите ответы.

Спасибо! Это класс, в котором мы узнаем, как на самом деле использовать рекурсию, поэтому я не думал о предыдущих экземплярах count. Я также обновил код в исходном сообщении, чтобы любой, кто нашел это, мог найти его более полезным. Закончилось просто подсчетом в массив, который передается.

Amethyst Espeon 02.11.2018 08:21

Другие вопросы по теме