Как случайно вставить узлы в двоичное дерево поиска? - PullRequest
Новая
       26

Как случайно вставить узлы в двоичное дерево поиска?

0 голосов
/ 08 апреля 2020

Я студент, изучающий структуры данных в Java. Я не новичок, поэтому, пожалуйста, не критикуйте мой код слишком сильно:).

Я хочу произвольно вставить узлы в двоичное дерево поиска, но не знаю, как это сделать, если не вручную ,

Я вставлю здесь метод Insert () и то, как я вставлял ранее. Также я получаю ошибку компиляции из-за сканера. Есть идеи почему? 

    {
        // Create node
        Node node = new Node(key, data);

        // Walk down the tree 
        Node parent = null;
        Node child = root;
        while (child != null)
        {
            // Parent goes down
            parent = child;

            // Child goes down
            if (key.compareTo(child.GetKey()) == 0)
                throw new RuntimeException("Duplicate key.");
            else if (key.compareTo(child.GetKey()) < 0)
                child = child.left;
            else
                child = child.right;        
        }

        // Hang new node from parent or make it the root
        node.parent = parent;
        if (parent == null)
            root = node;
        else if (key.compareTo(parent.GetKey()) < 0)
            parent.left = node;
        else
            parent.right = node;
    }




import java.util.Scanner;
class Test
{
    public static void main(String args[])
    {
        Tree tree = new Tree();

        // Create keys
        Node n1 = new Node(null, "1");
        Node n2 = new Node(null, "2");
        Node n3 = new Node(null, "3");
        Node n4 = new Node(null, "4");
        Node n5 = new Node(null, "5");
        Node n6 = new Node(null, "6");
        Node n7 = new Node(null, "7");

        // Create Scanner
        Scanner scanner = new Scanner();

        System.out.print("Enter 'sorted' or 'random': ");
        String s = scanner.nextLine();

        if (s == "sorted")
            tree.Insert("1", n1.GetData());
            tree.Insert("2", n2.GetData());
            tree.Insert("3", n3.GetData());
            tree.Insert("4", n4.GetData());
            tree.Insert("5", n5.GetData());
            tree.Insert("6", n6.GetData());
            tree.Insert("7", n7.GetData());

        if (s == "random")
            tree.Insert("5", n5.GetData());
            tree.Insert("2", n2.GetData());
            tree.Insert("1", n1.GetData());
            tree.Insert("3", n3.GetData());
            tree.Insert("6", n6.GetData());
            tree.Insert("7", n7.GetData());
            tree.Insert("4", n4.GetData());

        if (s != "random" && s != "sorted")
            throw new RuntimeException("Invalid input.");
    }
}

1 Ответ

0 голосов
/ 09 апреля 2020

В классе Collections имеется стандартный библиотечный метод для перемешивания списка. Чтобы использовать его, мы должны создать список с данными, а затем вызвать Collections.shuffle: 

List<String> data = new ArrayList();
for (int i = 1; i <= 7; i++) {
    data.add(String.valueOf(i));
}
Collections.shuffle(data);

Теперь вы можете просто вставить данные в дерево: 

for (String item: data) {
    tree.Insert(item, item);
}

Относительно ошибки компиляции не существует конструктора Scanner, который не принимает аргументов. Возможно, вы хотели передать системный стандартный поток ввода. 

    // Create Scanner
    Scanner scanner = new Scanner(System.in);

Еще одна вещь, которую я заметил: вы не можете сравнивать строки с ==, как в if (s == "sorted"), вместо этого вы должны использовать метод equals: if (s.equals("sorted"))

Еще одна вещь, вам нужно использовать скобки { } с операторами if. В противном случае то, что вы хотели запустить условно, будет работать всегда. 

    if (s == "sorted")
        tree.Insert("1", n1.GetData());
        tree.Insert("2", n2.GetData()); // <-- runs no matter what s is
...