Binärer Baum in Querrichtung

Question

Bitte jemand helfen; Ich glaube nicht, dass ich es richtig durchlaufe und es zurückkehrt, wenn es eine neue Liste zurückgeben muss. Ich bin seit einer Weile fest und muss noch alle anderen Durchgänge machen. Liefert Einheitentest für die benötigte Ausgabe, aber mein Komponententest ist möglicherweise falsch.

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

Es gibt zwei Probleme bei der Implementierung ab:

temp = [None] 

Die obige Anweisung erstellt eine Liste mit einem None Artikel:

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

Das zweite Problem ist Ihre Methode Logik anhängt; Sie geben die Werte zurück, anstatt sie anzufügen. Hier

ist eine Implementierung Basis auf Ihren Code:

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

Eine In-Order-Traversierung müsste in beide Teilbäume herunterkommen, falls vorhanden, und die Wurzel dazwischen besuchen; Ihr Code kehrt zurück, nachdem ein Teilbaum durchlaufen wurde, und überspringt den anderen Teilbaum und den Stamm.