我如何将节点随机插入二叉搜索树？

Question

我是一名学习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.");
    }
}

Answer 1

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