为什么我的辅助方法没有递归激活？

Question

我有一个二叉搜索树，我试图按顺序递归地跟踪树并将每个键、值附加到列表中。它只是将第一个键、值附加到列表中，而不是按顺序遍历列表。我在下面粘贴了我的代码，以及我在底部使用的测试代码。非常感谢任何有关如何解决此问题的帮助！

class TreeMap:
    class Node:
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.left = None
            self.right = None
    def __init__(self):
        self.root = None
        self.numsearches = 0
        self.numcomparisons = 0
    def add(self, newkey, newvalue):
        newkey = newkey.lower()
        if self.root == None:
            self.root = TreeMap.Node(newkey, newvalue)
        else:
            TreeMap.add_helper(self.root, newkey, newvalue)

    def add_helper(thisnode, newkey, newvalue):
        if newkey <= thisnode.key:
            if thisnode.left == None:
                thisnode.left = TreeMap.Node(newkey, newvalue)
            else:
                TreeMap.add_helper(thisnode.left, newkey, newvalue)
        else:
            if thisnode.right == None:
                thisnode.right = TreeMap.Node(newkey, newvalue)
            else:
                TreeMap.add_helper(thisnode.right, newkey, newvalue)
    
    def print(self):
        TreeMap.print_helper(self.root, 0)
    def print_helper(somenode, indentlevel):
        if somenode == None:
            print(" "*(indentlevel),"---")
            return
        if not TreeMap.isleaf(somenode):
            TreeMap.print_helper(somenode.right, indentlevel + 5)
            print(" "*indentlevel + str(somenode.key) + ": " +str(somenode.value))
        if not TreeMap.isleaf(somenode):
            TreeMap.print_helper(somenode.left, indentlevel + 5)
    
    def isleaf(anode):
        return anode.left == None and anode.right == None


    def listify(self, whichorder="in"):
        '''
        Returns a list consisting of all the payloads of the tree.  (This returns a plain old Python List.)
        The order of the payloads is determined by whichorder, which defaults to inorder.
        The other possibilities are "pre" and "post".
        If the tree is empty, return the empty list.
        '''
        assert type(whichorder) is str,"Whichorder is a string, and can only be pre, in or post"
        assert whichorder in ["pre","in","post"],"Whichorder is a string, and can only be pre, in or post"
        return TreeMap.listify_helper(self.root, whichorder)

    def listify_helper(somenode, whichorder):        
        order_list = []
        if somenode == None:
            return order_list
        elif somenode != None and whichorder == 'in':
            TreeMap.listify_helper(somenode.left, 'in')
            order_list.append(somenode.key+ '='+somenode.value)
            TreeMap.listify_helper(somenode.right, 'in')
        return order_list

测试代码：

import treemap

translator = treemap.TreeMap()

translator.add("cat", "Katze")
translator.add("bird", "Vogel")
translator.add("dog", "Hund")
translator.add("snake", "IDK")
translator.add("bear", "IDK")
translator.add("octopus", "Tintenfisch")
translator.add("horse", "Pferd")
translator.add("zebra", "IDK")

translator.print()
print("---------------------------------------------------")

print (translator.listify())

Answer 1

问题出在这里：

def listify_helper(somenode, whichorder):        
        order_list = []

这个函数每次被调用时都会初始化它自己的本地order_list。而是将 order_list 作为参数传递，以便每次递归调用都会附加相同的列表。

或者，将 listify_helper 的递归调用结果的每个元素附加到 order_list，尽管这种方法可能会导致不必要的复制。

为什么我的辅助方法没有递归激活？

Why is my helper method not activating recursively?

python

binary-search-tree

tree-traversal