0

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

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())
4

1 回答 1

1

问题在这里：

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

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

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

于 2021-05-13T03:52:18.620 回答