超过Python树遍历递归深度

我有一个段树保存数据范围的数据（数据结构选择here）。代码如下：超过Python树遍历递归深度

class SegmentTree: 
    def __init__(self, N): 
     def _init(b, e): 
      if b is e: 
       data = foo() # No dependency 
       return Node(b, e, data, None, None) 
      else: 
       mid = (b + e)/2 

       L = _init(b, mid) 
       R = _init(mid + 1, e) 

       data = foo() #Data depends on L and R 

       return Node(b, e, data, L, R) 

     self.root = _init(1, N)

对于N在300附近，最大递归深度超过错误，此失败。有没有办法迭代创建树而不是递归？

来源

2011-10-09 knite

真正的问题不在于算法的递归深度，对于像300这样的值，应该是大约10，但是您要将数字与is进行比较。该is关键字检查对象的身份，而==检查平等：

>>> 300 == 299+1 
True 
>>> 300 is 299+1 
False

因为你if条件应当终止递归永远不会为真和功能将保持递归，即使b和e相等。

如果更改if这个问题就会消失：

if b == e: 
    ...

对于小的数字可能不会出现因为Python "caches" and reuses the objects为整数达到一定规模的问题。

来源

2011-10-09 17:42:16 sth

通常，您从递归转换为迭代的方式是手动维护堆栈（或队列）。

喜欢的东西：

while stack is not empty: 
    item = pop from stack 

    do processing (such as adding onto the node) 

    push L and R onto the stack

堆栈并在内存中成长，因为你如雨后春笋般冒出的每个项目，你正在推动两项。

来源

2011-10-09 17:26:46

是的，我想这样做，但我需要在（递归）创建L和R节点之后在当前节点上执行我的处理。我不确定在何处/如何将当前节点存储以供将来处理 - 在单独的堆栈上？ – knite

那么通常有更好的方法来实现树遍历（尽管它们可以通过指针旋转和东西变得复杂）而不是使用“栈”。毕竟，如果你在堆上使用堆栈，你实际上并没有节省太多空间（除了一个常数因子，因为你需要节省更少的状态） – Voo

超过Python树遍历递归深度

回答

相关问题