將Splay Tree中的1,000,000個節點轉換爲SinglyLinkedList時出現StackOverFlow錯誤

我已經實現了一個使用節點存儲數據的Splay Tree類。在這個類中，我嘗試將節點的數據轉換爲單鏈表。可以將100萬個節點插入到splay樹中，並且完美地工作。使用遞歸時，當樹包含1,000,000個節點時，會出現StackOverFlow錯誤。但是，如果樹包含大約15000個節點，則它可以毫無問題地轉換爲鏈接列表。將Splay Tree中的1,000,000個節點轉換爲SinglyLinkedList時出現StackOverFlow錯誤

這裏是我的toList方法的代碼是在伸展樹類內部

public LinkedList<Node> toList() { 

    LinkedList<Node> list = new LinkedList<Node>(); 
    Node node = root; 
    addToList(node, list); 

    return list; 
} 

private void addToList(Node node, LinkedList<Node> list) { 
    if(node != null) { 
     addToList(node.left, list); 
     list.add(node); 
     addToList(node.right, list); 
    } 
}

我用下面這個測試類來測試該方法

@Test 
public void testConversionToLinkedList { 
    SplayTree<Integer,String> st = new SplayTree<Integer,String>(); 
    for(int i = 0; i < 1000000; i++) { 
     st.insert(i, Integer.toString(i)); 
    } 
    assertEquals(1000000, st.size()); 

    LinkedList<Node> list = st.toList(); 
    assertEquals(1000000, list.size()); 
}

測試通過時的功能輸入的大小約爲15000，然而任何大於該值的數字都將顯示StackOverFlowError

錯誤發生在行addToList(node.left, list);

這真的很奇怪，因爲當我使用相同的遞歸技術將節點的數據打印到txt文件時，沒有出現StackOverFlow錯誤並且數據打印完美。

我試圖使用在訂單遍歷，PreOrder和PostOrder但我仍然收到在1,000,000節點相同的錯誤。我知道它可能會太深入地進行遞歸，並且堆棧內存不足。如果是這種情況，我有什麼辦法可以將節點的一個splay樹轉換成一個鏈表？任何想法可能會出錯？歡呼聲

來源

2017-10-11 Yanzal

你的問題是遞歸算法。正如你所想的那樣，堆棧大小有一個限制，當你有遞歸時，堆棧大小會被建立。

您始終可以將遞歸轉換爲循環。

這裏是使用循環DFS和BFS算法的一些例子：Non recursive Depth first search algorithm

來源

2017-10-11 08:33:54 Sorontur

可以增加堆棧的大小。要做到這一點，你必須將參數傳遞給jvm。格式爲-Xss [g | G | m | M | k | K]。例如：java -Xss4m YourTreeProgram

來源

2017-10-11 08:38:45 niemar

將Splay Tree中的1,000,000個節點轉換爲SinglyLinkedList時出現StackOverFlow錯誤

回答

相關問題