在python中将递归的setitem转换为迭代的

Question

这里有我的二叉搜索树的setitem方法。我现在得到了“RecursionError:maximum recursion depth exceeded”错误，所以我想把它转换成一个迭代方法，但我有点卡住了。有什么提示吗？你知道吗

class BinarySearchTreeNode:

    def __init__(self, key, item=None, left=None, right=None):
        self.key = key
        self.item = item
        self.left = left
        self.right = right

class BinarySearchTree:

    def __init__(self):
        self.root = None

    def __setitem__(self, key, item):
        self.root = self._setitem_aux_(self.root, key, item)

    # here convert this to an iterative method
    def _setitem_aux_(self, current, key, item):
        if current is None:
            current = BinarySearchTreeNode(key, item)
        elif key < current.key:
            current.left = self._setitem_aux_(current.left, key, item)
        elif key > current.key:
            current.right = self._setitem_aux_(current.right, key, item)
        else: # key == current.key
            current.item = item
        return current

并称之为：

bst = BinarySearchTree() 
# To set an item with key = 0, item = 1
bst[0] = 1 
# To set an item with key = "abcd", item = 10
bst["abcd"] = 10

Answer 1

也许试试这个？你知道吗

def __setitem__(self, key, item):
    if self.root is None:
        self.root = BinarySearchTreeNode(key, item)
    else:
        current = self.root
        found = False
        max_iter = 10000  # set this to the appropriate value for your use case
        iter_ = 1
        while not found and iter < max_iter:
            if current is None:
                raise IndexError("Index out of bounds")
            elif key < current.key:
                current = current.left
            elif key > current.key:
                current = current.right
            else:
                found = True
            iter_ += 1

        if found:
            self.root = current
        else:
            raise IndexError("Index too far from root")

注：递归是一种强大但危险的模式。它也会阻碍代码的可读性。当一段迭代代码可以获得相同的结果时，应该避免这种情况。你知道吗