Обход двоичного дерева в Python

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

Обход по порядку должен спускаться в оба поддеревья, если они присутствуют, и посещать корень между ними; Ваш код возвращается после обхода поддерева, пропуская другое поддерево и корень.