Поиск в ширину не возвращает правильный порядок узлов - PullRequest
Новая
       69

Поиск в ширину не возвращает правильный порядок узлов

1 голос
/ 13 июля 2020

Я реализовал дерево, которое выглядит так: 

               1

    2          3          4

 5     6               7      8

Я хочу распечатать его по ширине. Это мой код: 

class Node:
    def __init__(self):
        self.data = None
        self.children = []


class Tree:
    def __init__(self):
        self.root = Node()

    def build(self):
        self.root.data = 1
        self.root.children.append(Node())
        self.root.children.append(Node())
        self.root.children.append(Node())
        self.root.children[0].data = 2
        self.root.children[1].data = 3
        self.root.children[2].data = 4

        self.root.children[0].children.append(Node())
        self.root.children[0].children.append(Node())

        self.root.children[2].children.append(Node())
        self.root.children[2].children.append(Node())

        self.root.children[0].children[0].data = 5
        self.root.children[0].children[1].data = 6

        self.root.children[2].children[0].data = 7
        self.root.children[2].children[1].data = 8
        return


    def traverseBF(self, node):
        li = []
        trav = []
        li.append(node)
        while len(li) != 0:
            for x in li:
                trav.append(x.data)
                for z in x.children:
                    li.append(z)
                # map(lambda z: li.append(z), x.children)
                li.remove(x)
        print(trav)



t = Tree()
t.build()
t.traverseBF(t.root)

Результат: [1, 3, 2, 5, 4, 7, 6, 8]

Мои вопросы:

  1. Почему 3 вставляется в trav [] перед 2, хотя в root .children порядок [2,3,4]
  2. Почему закомментированная функция карты не дает те же результаты, что и для l oop выше?

1 Ответ

1 голос
/ 13 июля 2020

Проблема в том, как вы управляете своей очередью. Используйте одиночный while l oop, который проверяет длину списка. В это время вытолкните первый узел, а затем расширьте очередь дочерними элементами вытолкнутого узла. Ваша функция должна выглядеть так: 

def traverseBF(self, node):
    li = []
    trav = []
    li.append(node)
    while len(li) != 0:
        x = li.pop(0)          # pop the first item
        li.extend(x.children)  # extend the queue with children
        trav.append(x.data)
    print(trav)

Здесь t.traverseBF(t.root) печатает [1, 2, 3, 4, 5, 6, 7, 8].

Вот «более чистая» версия вашего кода. Мне нравятся генераторы, поэтому я превратил его в генератор, который один за другим возвращает значения узлов в порядке BFS: 

def bfs(node):
    q = [node]
    while q:
        n = q.pop(0)
        q.extend(n.children)
        yield n.data

[*bfs(t.root)]
# [1, 2, 3, 4, 5, 6, 7, 8]
...