Что не так с этой реализацией DFS?

Question

Я не уверен, что не так со следующим кодом поиска в глубину. Ожидаемый выходной результат программы включен в конце. Я получил ожидаемый результат, запустив код от geeksforgeeks (s / o к ним). Любая помощь будет оценена. Вот мой код:

class Node:
    def __init__(self, val):
        self._val = val
        self._chdrn = []

class Nary:

    def __init__(self, n: int):
        self._n = n
        self._root = None

    def insert(self, val: int):
        nn = Node(val)
        if not self._root:
            self._root = nn
        else:
            def recur(parent: Node):
                print("Parent: ", parent._val)
                if len(parent._chdrn) < self._n:
                    parent._chdrn.append(nn)
                    return 1
                else:
                    for chdl in parent._chdrn:
                        ret = recur(chdl)
                        if ret == 1:
                            break
            parent = self._root
            recur(parent)

    def dfs(self):
        def _dfs(node: Node):
            if not node: return
            print(node._val, end=' ')
            for chld in node._chdrn:
                # print("current child = ", chld._val)
                _dfs(chld)
        _dfs(self._root)

Tree  = Nary(3)
for i in range(10): Tree.insert(i)
Tree.dfs()

#

Ожидаемый результат: 0 1 4 5 6 2 7 8 9 3
Выход программы: 0 1 4 7 8 9 5 6 2 7 8 9 3

Answer 1

Ничего не помешает вашему коду DFS. Ваше древовидное построение методом insert неверно.

Вам нужно возвращаться в рекурсивном случае при циклическом просмотре потомков в recur. В противном случае один и тот же узел будет вставлен под несколькими родителями.

class Node:
    def __init__(self, val):
        self._val = val
        self._chdrn = []


class Nary:

    def __init__(self, n: int):
        self._n = n
        self._root = None

    def insert(self, val: int):
        print(f"Inserting {val}")
        nn = Node(val)
        if not self._root:
            self._root = nn
        else:
            def recur(parent: Node):
                if len(parent._chdrn) < self._n:
                    print(f"Added under parent: {parent._val}")
                    parent._chdrn.append(nn)
                    return 1
                else:
                    for chdl in parent._chdrn:
                        ret = recur(chdl)
                        if ret == 1:
                            return 1  # not just break

            parent = self._root
            recur(parent)

    def dfs(self):
        def _dfs(node: Node):
            if not node: return
            print(node._val, end=' ')
            for chld in node._chdrn:
                # print("current child = ", chld._val)
                _dfs(chld)

        _dfs(self._root)


Tree = Nary(3)
for i in range(10): Tree.insert(i)
Tree.dfs()

Кстати, правильный порядок DFS для этого дерева:

0 1 4 7 8 9 5 6 2 3 

Вы должны нарисовать дерево и вручную выполнить DFS для проверки.