将展开树中的1,000,000个节点转换为SinglyLinkedList时出现StackOverFlow错误

Question

我已经实现了一个使用节点来存储数据的Splay Tree类。在这个类中，我尝试将节点的数据转换成一个单链表。可以将1,000,000个节点插入到展开树中，并且它可以完美地工作。使用递归时，当树包含1,000,000个节点时，我得到一个StackOverFlow错误。但是，当树包含大约15000个节点时，可以将其转换为链表，这是没有问题的。

下面是我的toList方法的代码，该方法位于splay树类中

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个节点上仍然收到相同的错误。我知道它可能会做太深的递归，导致堆栈耗尽内存。如果是这种情况，有没有什么方法可以将节点的展开树转换为链表？你知道会出什么问题吗？干杯

Answer 1

你的问题是递归算法。正如您所计算出的那样，堆栈大小是有限制的，这是在使用递归时构建的。

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

以下是使用循环的DFS和BFS算法的一些示例：Non recursive Depth first search algorithm

Answer 2

您可以增加堆栈的大小。为此，您必须将参数传递给jvm。格式为-Xssg|G|m|M|k|K。例如: java -Xss4m YourTreeProgram