在Python中二进制树inorder遍历

Question

我不认为我正确地遍历它并且当它需要返回一个新列表时它返回空.我已经被困了一段时间,仍然需要做所有其他的遍历.将为所需的输出提供单元测试,但我的单元测试可能是错误的.

def inorder(self):

    print("in INOrDER is entered")
    temp = [None]


    if self.__left:
        temp = temp.append(self.__left)
        return self.__left.inorder() 
    elif self.__right: 
        temp = temp.append(self.__right)
        return self.__right.inorder() 
    return temp


def test_inorder(self):
    bt = family_tree()
    bt.add(20, "melanie")
    bt.add(10, "edwin")
    bt.add(30, "junior")
    bt.add(25, "dora")
    bt.add(35, "kate")
    x = bt.inorder()

    expected = '''(10, 'edwin'),(20, 'melanie'),(25, 'dora'),(30, 'junior'),(35, 'kate')'''
    self.assertEquals(str(x), expected)
    t = family_tree(bt)
    self.assertEquals(str(t), expected)

Answer 1

您的实施中存在两个问题:

temp = [None]

上面的语句创建了一个包含None项目的列表:

x = len(temp) # x value will be 1

第二个问题是你的方法附加逻辑; 你返回值而不是追加它们.

以下是您的代码的实现:

def inorder(self):
    result = []
    if self.__left:
        result += self.__left.inorder()

    result.append(self.__value)

    if self.__right:
        result += self.__right.inorder()

    return result