二分查找树

Question

嗨，我有一个数组列表，里面有一些数字，比如{23,16,45,26,2,5,9}，我想用这个数组列表做一个二进制搜索树，它是"array"，它的元素是有2字段的对象，1)digit2)level，但这里我只想用它的digit field.Also dList is a DoublyLinkedList。这是我的代码，但它会抛出一个exception.please帮助我，谢谢。

    private void method(ArrayList<Element> array) {
    DNode header = new DNode(null, null, null);
    DNode trailer = new DNode(null, header, null);
    header.next = trailer;
    DNode node = new DNode(array.get(0), header, trailer);
    dList.addLast(node);
    header = node
    for(int i = 1;i<array.size();i++){
    makeBST(node, array.get(i));
    }
}

private void makeBST(DNode node, Element e) {

    if (!e.equals(node.getElement())) {
        DNode nodeOne = new DNode(e, null, null);
        if (node.getElement().getDigit() > e.getDigit()) {
            node.prev = nodeOne;
        } else if (node.getElement().getDigit() < e.getDigit()) {
            node.next = node;
        }
    }
    if (e.getDigit() < node.getElement().getDigit()) {
        makeBST(node.prev, e);
    }
    makeBST(node.next, e);
}

例外：

Exception in thread "main" java.lang.StackOverflowError
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:43)
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:54)
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:54)
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:54)

第一行异常适用于下面这行代码：

if (!e.equals(node.getElement())) 

Answer 1

您的递归方法"private void makeBST(DNode node，Element e)“需要某种类型的结束条件(一个流路径，它将阻止它调用自己)；实际上，它一直递归地调用自己，这就是导致堆栈溢出错误的原因。

Answer 2

你的代码基本上是：

private void makeBST(DNode node, Element e) {
    // ... (the rest of your code)
    makeBST(node.next, e);
}

它几乎等同于：

private void makeBST(DNode node, Element e) {
    while(true) {
        // ... (the rest of your code)
        node = node.next;
    }
}

您刚刚创建了一个无限循环(但不是使用while，而是使用递归)。因为堆栈的大小非常有限，所以经过一些迭代后，您会得到StackOverflowError。

但不管怎样，如果这只是一个教育实验，那也没问题。如果您只需要一个有效的BST，那么可以使用java.util.TreeSet或java.util.TreeMap。

Answer 3

您得到了一个StackOverflowError，它指向一个无限(至少是潜在的)递归错误。

附注：为什么不使用TreeMap，其中K是数据的索引，V是数据值？