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

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 class 中有一个标准库方法来打乱列表。要使用它，我们必须用数据创建一个列表，然后调用 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

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

How do I randomly insert nodes into a binary search tree?

java

insert

binary-search-tree