java - 二叉搜索树

Question

嗨我有一个数组列表，其中包含一些数字，例如 {23,16,45,26,2,5,9}我想用这个数组列表创建一个二叉搜索树，它是 "array" ，它的元素是具有 2 字段的对象，1)digit2)level 但在这里我只想使用它的 digit 字段。另外 dList 是一个 DoublyLinkedList。这是我的代码，但它会抛出异常。请帮助我，谢谢。

    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):

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)”需要某种类型的结束条件(一个阻止它调用自身的流路径)；事实上，它不断递归地调用自身，这就是导致堆栈溢出错误的原因。