使用队列的非二叉树中的BFS/级顺序遍历

Question

我必须创建两个类:NonBinaryTree和SingleNode类，包含一些处理节点和整个树的方法(在NonBinaryTree类中)。我在使用队列(先进先出类型)实现非二叉树的BFS(层次顺序)遍历时遇到过问题。由于二叉树有很多资源，每个节点最多有两个子节点，我还没有找到任何可以帮助我解决非二叉树问题的资源。

到目前为止，我做了这个代码：

import queue
from typing import List, Callable


class SingleNode:
    def __init__(self, name : str):
        self.name : str = name
        self.children : List['SingleNode'] = []

    def add(self, *nodes : List['SingleNode']):
        for node in nodes:
            self.children.append(node)

    def is_leaf(self):
        if len(self.children) == 0:
            return True
        return False

    def level_order_traversal(self, visit: Callable[['SingleNode'], None]) -> List[List[int]]:
        fifo = queue.Queue()
        levels = []
        fifo.put([root])
        while fifo and root:
            currNode, nextLevel = [], []
            while not fifo.empty():
                node = fifo.get()
                currNode.append(node)
                for child in node.children:
                    nextLevel.append(child)
            fifo.put(nextLevel)
            levels.append(currNode)
        return levels

    def search(self, name : str):
        if self.name == name:
            print(self.__repr__())
        for child in self.children:
            child.search(name)
        return None

    def __str__(self):
        return f"{self.name}"

    def __repr__(self):
        return f"TreeNode({self.name}) : {self.children}"
        
        
class NonBinaryTree:
    root_node: SingleNode

我的树：

在此处输入图像描述

我需要按以下顺序处理节点:1、2、3、4、5、6、7、8等等...

Answer 1

你为什么不遵循类似于二叉树中BFS遍历的方法，只是在这种情况下它是非二进制的，但逻辑总是相同的，

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        levels = []
        queue = [root]
        while queue and root:
            currNode,nextLevel = [],[]
            for node in queue:
                currNode.append(node.val)
                for child in node.children:
                    nextLevel.append(child)
            queue = nextLevel
            levels.append(currNode)
        return levels