Небинарный метод обхода дерева

Я пытаюсь создать класс небинарного дерева Python с методами, которые позволят мне получить определенные узлы и применить другие методы к этим найденным узлам.

Я начал с кода из этого очень красивого примера: https://www.youtube.com/watch?v=4r_XR9fUPhQ

Я добавил метод, который принимает строку, соответствующую узлу (разделенному /, пропуская корень), который я ищу, рекурсивно ищет дерево и теоретически возвращает узел, используя себя, чтобы я мог применить к нему другой метод.

Однако, когда я возвращаю (я), он возвращает мне нетип вместо узла.

Совет о том, как это исправить, или предложение другого пути, если это плохой способ структурировать вещи, будут очень признательны!

Заранее спасибо.

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

Код ниже:

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.children = []
        self.parent = None
        self.forecast = None

    def get_level(self):
        level = 0
        p = self.parent
        while p:
            level += 1
            p = p.parent

        return level

    def print_tree(self):
        spaces = ' ' * self.get_level() * 3
        prefix = spaces + "|__" if self.parent else ""
        print(prefix + self.data)
        if self.children:
            for child in self.children:
                child.print_tree()


    def get_node(self, path):
        segs = path.split('/')
        sep = "/"
        print(self.return_child_names())
        if self.children:
            for child in self.return_child_names():
                if segs[0] == child:
                    found_child = segs.pop(0)
                    break
            self.children[self.return_child_names().index(found_child)].get_node(sep.join(segs))
        else:
            print("Found the node!")
            print(self)
            print(self.data)
            return(self)

    def return_child_names(self):
        return([c.data for c in self.children])

    def add_child(self, child):
        child.parent = self
        self.children.append(child)




def build_product_tree():
    root = TreeNode("Electronics")

    laptop = TreeNode("Laptop")
    laptop.add_child(TreeNode("Mac"))
    laptop.add_child(TreeNode("Surface"))
    laptop.add_child(TreeNode("Thinkpad"))

    cellphone = TreeNode("Cell Phone")
    cellphone.add_child(TreeNode("iPhone"))
    cellphone.add_child(TreeNode("Google Pixel"))
    cellphone.add_child(TreeNode("Vivo"))

    tv = TreeNode("TV")
    tv.add_child(TreeNode("Samsung"))
    tv.add_child(TreeNode("LG"))

    root.add_child(laptop)
    root.add_child(cellphone)
    root.add_child(tv)

    root.print_tree()

    return(root)

product_tree = build_product_tree()

product_tree.get_node("Laptop/Mac").print_tree()

person Ian O'Reilly    schedule 25.09.2020    source источник
comment
У вас нет return в блоке if self.children. Вы должны вернуть результат рекурсивного вызова.   -  person trincot    schedule 25.09.2020
comment
Интересно, спасибо за отзыв! Когда я добавляю оператор возврата после рекурсивного вызова, я получаю результат, но результатом является верхний узел дерева, а не найденный мною узел, который соответствует моему пути... Это потому, что он возвращается на первый вызов get_node?   -  person Ian O'Reilly    schedule 25.09.2020
comment
Убедитесь, что не return self, а return self.children[......   -  person trincot    schedule 25.09.2020
comment
Понятно! Большое спасибо!   -  person Ian O'Reilly    schedule 26.09.2020


Ответы (1)


Проблема в функции get_node: вы не всегда возвращаете значение. Примечательно, что в следующем блоке нет return, поэтому функция может вернуть None:

if self.children:
    for child in self.return_child_names():
        if segs[0] == child:
            found_child = segs.pop(0)
            break
    self.children[self.return_child_names().index(found_child)].get_node(sep.join(segs))

Значение, которое вы получаете от рекурсивного вызова get_node, игнорируется. Вы должны вернуть его:

    return self.children[self.return_child_names().index(found_child)].get_node(sep.join(segs))
person trincot    schedule 26.09.2020