二叉搜索树

嗨我有其中有几个电话号码，它像{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 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()))

来源

2010-12-13 user472221

您的递归方法 “私人无效makeBST（DNode节点，元素E）”需要一些类型的结束条件（一个流程路径，它会阻止它自己调用）;因为它是，它不断调用自己递归这是什么导致你的堆栈溢出错误。

来源

2010-12-13 15:33:55 Assaf

我该如何完成递归调用？ – user472221 2010-12-13 15:38:21

我想你需要在第一个if块的末尾有一个“return”。或者，如果结果相同，则可以将递归makeBST调用放入适当的“else if”块中。 – TToni 2010-12-13 15:41:38

@ user472221，TToni和iirekm已经说得对。对于递归结束条件，你需要考虑什么时候递归需要停止（提示：当你有一棵大小为0或者大小为1的树时会发生什么？），并且当这个条件被命中时，你需要确保函数停止调用自己。 – Assaf 2010-12-13 15:52:49

你有一个StackOverflowError，它指向一个无限的（可能至少有）递归错误。

p.s.为什么不只是使用TreeMap<K,V>其中K是数据的索引，V是数据值？

来源

2010-12-13 15:34:10

你的代码基本上是：

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; 
    } 
}

你只是做一个无限循环（但不能与一段时间，但用递归）。由于堆栈大小非常有限，经过一些迭代后，您会收到StackOverflowError。

但无论如何，如果它只是一个教育实验，那就没关系。如果您只需要一个可用的BST，请使用java.util.TreeSet或java.util.TreeMap。

来源

2010-12-13 15:49:42 iirekm

如何使用treeSet或treeMap制作BST？你能帮我吗？ – user472221 2010-12-13 16:05:08

我可以看到您正在尝试，但距离解决方案还很遥远。

你正在使用递归，所以你需要一个停止的情况......你没有。

你也应该可能有，如果...否则，如果...而不是你所拥有的（如果...如果...）

那行if (!e.equals(node.getElement())) { 是没有意义要么...

查看关于二叉树和二叉搜索树的维基百科文章......可能会有所帮助。

来源

2010-12-13 16:38:58

回答

相关问题