二叉搜索樹

嗨我有其中有幾個電話號碼，它像{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

回答

相關問題