二叉树中序横向

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

有2个问题，在您的实现：

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 

Answer 2

有序遍历需要下降到两个子树中（如果存在的话），然后访问它们之间的根;遍历子树，跳过其他子树和根后您的代码返回。