返回列表的二叉搜索树的有序遍历

Question

在遍历BST之后，我需要返回一个有序的引用列表，并且它们之间有一个空，但我无法锻炼该怎么做。

def inorder(self, Node):

    res = ""
    if Node != None:

        self.inorder(Node.LeftChild())
        res = res +(Node.key + " " + Node.payload + "\n")
        self.inorder(Node.RightChild())

    return res

这是我的代码，到目前为止，我只能得到一个参考，任何帮助将不胜感激。

Answer 1

您几乎完全正确，只需要在res变量中使用左右子树的返回值

def inorder(self, Node):

    res = ""
    if Node != None:

        lres = self.inorder(Node.LeftChild())
        rres = self.inorder(Node.RightChild())
        res = lres + (Node.key + " " + Node.payload + "\n") + rres

    return res

注意：res在您的情况下始终为空字符串，因此您不需要执行res = res+，也有用于执行此res+=的简写形式，但无论如何您都不需要它。

Answer 2

类似于注释中的@Lesiak，您应该通过将它们与当前节点的输出连接起来来利用对inorder的递归调用的返回值：

def inorder(self, Node):
    if Node is None:
        return ""
    return f'{self.inorder(Node.LeftChild())}{Node.key} {Node.payload}\n{self.inorder(Node.RightChild())}'

或：

def inorder(self, Node):
    if Node is None:
        return ""
    return f'{Node.key} {Node.payload}\n'.join(map(self.inorder, (Node.LeftChild(), Node.RightChild())))