проблема со списком в рекурсии для обхода двоичного дерева

Question

Я пытаюсь использовать рекурсию для обхода двоичного дерева. У каждого дерева либо есть два дочерних элемента, либо нет дочерних (то есть поля, зарезервированные для дочерних элементов == Нет)

Я хотел бы добавить последние листья каждой ветви (то есть каждого узла, чей два ребенка == Нет) к списку и вернуть список. Я делаю это с помощью функции 'search' и вспомогательной функции 'search_base'.

Через отладчик я вижу, что список в функции «поиск» действительно содержит элементы, которые я хочу. Но когда он возвращается в функцию search_base, результат кажется пустым списком.

Я очень запутался и был бы благодарен за любую помощь. Спасибо!

class Node:
    def __init__(self, data, pos = None, neg = None):
        self.data = data
        self.positive_child = pos
        self.negative_child = neg   

class Diagnoser:
    def __init__(self, root):
        self.root = root

    def search_base(self):
        leaf_list=[]
        current = self.root
        return self.search(current, leaf_list)

    def search(self, current, leaf_list):
        if(current.positive_child == None):
            leaf_list.append(current)
            return leaf_list
        else:
            self.search(current.positive_child, leaf_list)
            self.search(current.negative_child, leaf_list)


if __name__ == "__main__":

    # Manually build a simple tree.
    #                cough
    #          Yes /       \ No
    #        fever           healthy
    #   Yes /     \ No
    # influenza   cold

    flu_leaf = Node("influenza", None, None)
    cold_leaf = Node("cold", None, None)
    inner_vertex = Node("fever", flu_leaf, cold_leaf)
    healthy_leaf = Node("healthy", None, None)
    root = Node("cough", inner_vertex, healthy_leaf)

    diagnoser = Diagnoser(root)
    leaf_list = diagnoser.search_base()
    print(leaf_list[0].data)

Answer 1

Проблема в том, что в

self.search(current.positive_child, leaf_list)
self.search(current.negative_child, leaf_list)

Возвращаемые значения из этих операторов не сохраняются и не возвращаются, поэтому здесь функция выдает None. Кроме того, leaf_list, передаваемый в оба этих оператора, одинаков, то есть они не объединяются. В рекурсивных функциях вам лучше не иметь побочных эффектов, чтобы сохранить его в безопасности. Должно быть:

 def search(self, current, leaf_list=[]):
        if(current.positive_child == None):
            return [current]
        else:
            return (self.search(current.positive_child, leaf_list)
                    + self.search(current.negative_child, leaf_list))

Answer 2

Вот более простое решение без побочных эффектов:

class Node:
    def __init__(self, data, pos=None, neg=None):
        self.data = data
        self.positive_child = pos
        self.negative_child = neg

    def leaves(self):
        if self.positive_child is self.negative_child is None:
            return [self]
        else:
            return (self.positive_child.leaves() +
                    self.negative_child.leaves())


if __name__ == "__main__":
    # Manually build a simple tree.
    #                cough
    #          Yes /       \ No
    #        fever           healthy
    #   Yes /     \ No
    # influenza   cold

    flu_leaf = Node("influenza", None, None)
    cold_leaf = Node("cold", None, None)
    inner_vertex = Node("fever", flu_leaf, cold_leaf)
    healthy_leaf = Node("healthy", None, None)
    root = Node("cough", inner_vertex, healthy_leaf)
    for leaf in root.leaves():
        print(leaf.data)

Answer 3

Поскольку search изменяет список, ему не нужно ничего возвращать, а search_base может просто вернуть измененный список.

class Diagnoser:
    def __init__(self, root):
        self.root = root

    def search_base(self):
        leaf_list = []
        current = self.root
        self.search(current, leaf_list)
        return leaf_list

    def search(self, current, leaf_list):
        if current.positive_child is None:
            leaf_list.append(current)
        else:
            self.search(current.positive_child, leaf_list)
            self.search(current.negative_child, leaf_list)

Кроме того, вам нужно проверить, что оба потомка отсутствует, т.е.

if current.positive_child is None and current.negative_child is None: