java - 输入元素时进行二叉树排序

Question

我是学习java的新手。我想制作对元素进行排序的二叉树

我使用了这个代码

private void setNode (Node Value, Node head){

    if (head == null || Value.Value == head.Value)
        return;

        if (Value.Value > head.Value) {
            if (head.Right == null) {
                head.Right = Value;
                return;
            } else
                setNode(Value, head.Right);
        }

    if (Value.Value < head.Value){
        if(head.Left == null){
            head.Left = Value;
            return;}
        else
            setNode(Value, head.Left);
    }

}

但是如果我像这样使用它

for (int i=0 ; i < array.length ; i++)
        link.addNode(new Node(i));

BinaryLinkList a = new BinaryLinkList(link);
    a.Search(700);

700次尝试后会找到它因为每次输入的数字都比前一次大会是这样的

0

.1

..2

...3

....4

.....5

......

......

......700 <<

……

......1000

我希望它在逐一输入元素而不是数组时进行排序有什么帮助吗？

Answer 1

二叉树一般概念的最坏情况是按排序顺序插入元素。然后，您将完全体验到您刚才告诉我们的内容，所有元素都将被放置到一侧，并且您不会从树概念中获得任何优势(深度是元素的数量)。

对于可能已经排序的输入进行排序，您应该使用二叉树之外的其他数据结构，有许多具有不同优点和缺点的概念。

还有一个优化，可以在一段时间后平衡树。正如@Kevin Anderson提到的，你可以看看 self balancing binary trees 。标准 Java 库附带的实现也是 self 平衡的 ( TreeSet at JavaAPI )。也许您也在寻找 PriorityQueue ( PriorityQueue at JavaAPI )。关于如何实现此类队列(例如 BucketQueue)也有多种概念，同样各有优缺点。

您的用户案例是什么？如果您告诉我们您想用它来实现什么，我们可以帮助您找到合适的数据结构。