将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树转换成一个链表？任何想法可能会出错？欢呼声

答

你的问题是递归算法。正如你所想的那样，堆栈大小有一个限制，当你有递归时，堆栈大小会被建立。

您始终可以将递归转换为循环。

这里是使用循环DFS和BFS算法的一些例子：Non recursive Depth first search algorithm

答

可以增加堆栈的大小。要做到这一点，你必须将参数传递给jvm。格式为-Xss [g | G | m | M | k | K]。例如：java -Xss4m YourTreeProgram

将Splay Tree中的1,000,000个节点转换为SinglyLinkedList时出现StackOverFlow错误

相关推荐