二叉樹中序橫向

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

有序遍歷需要下降到兩個子樹中（如果存在的話），然後訪問它們之間的根;遍歷子樹，跳過其他子樹和根後您的代碼返回。