如何在BFS中遍历时存储每个节点的级别？
如果我们有二叉树：
7 / \ 5 6 /\ /\ 2 3 1 4 / 5 如何打印以下输出？
[7], [5,6] [2,3,1,4] [5]
意味着做一个BFS并在列表中的每个级别存储节点，然后打印列表？
我能够在BFS中遍历，但我无法在树中找到每个元素的正确级别。
如何找到每个节点的正确级别并使用其级别值丰富节点对象？
这是我的逻辑：
-
遍历BFS
-
使用其级别值丰富树的每个节点
-
将节点存储在列表中
-
遍历列表并创建
<Level,List>的Map -
将节点级别存储在
Set，然后转换为列表并对其进行排序。 -
迭代新创建的级别列表，并从地图中找到该列表上的相应节点并打印它
Tree遍历将是：
7 – 5 – 7 – 6 – 7 – 5 – 2 – 5 – 3 – 5 – 3 – 5 – 7 -6 – 1 – 6 – 4
逻辑是。
总是选择左孩子如果你不能选择一个孩子，请选择一个合适的孩子如果你不能选择任何一个孩子，那就去找父母吧
在打印方面，跟踪您访问过的节点，如果您访问过它们，则不要打印它们，这样就不会打印“后退跟踪”
您的节点（伪代码）应如下所示：
Node { Node *parent; Node *child_left; Node *child_right; Boolean visited; int level; }
每个节点都应该有一个父节点（根节点除外），并且可以选择有子节点。 一旦你遍历它，设置访问为真。
当你下一个级别（即访问一个孩子）时，你应该增加一个global_level变量。 当你回去（即访问父母）你应该减少它。
就将它们存储在列表中而言，您可以只拥有一个全局列表，只需在已经访问过的情况下不要推送它。
使用BFS遍历。
有2个计数 – 一个是当前级别中剩余的节点数（从1开始）和下一级别的剩余节点数（从0开始）。
每当处理节点时，减少当前级别计数，并增加添加到队列的每个子级的下一级别计数。
如果当前级别计数变为0，则启动新列表。 将当前级别计数设置为下一级别计数，并将当前级别计数设置为0。
你的树例如：
Current level count = 1 Next level count = 0 Queue: 7 Dequeue 7, enqueue 5 and 6. Current list: [7] Current level count = 1 - 1 = 0 Next level count = 0 + 2 = 2 Current level count == 0, so Current level count = Next level count = 2 Next level count = 0 Finished with [7], starting a new list Queue: 5, 6 Dequeue 5, enqueue 2 and 3. Current list: [5] Current level count = 2 - 1 = 1 Next level count = 0 + 2 = 2 Queue: 6, 2, 3 Dequeue 6, enqueue 1 and 4. Current list: [5, 6] ...
假设树中的所有节点都是从1到n，我们可以使用两个数组来存储节点的级别。
int [] parent = new int[n + 1];//To store the direct parent of the current node int [] level = new int[n + 1];//To store the level of the current node
从根级别0开始，索引7将具有值level[7] = 0 ; 它的两个孩子5和6将有parent[5] = 7 and parent[6] = 7 ; 类似地， level[5] = level[parent[5]] + 1和level[6] = level[parent[6]] + 1 。
通过这些步骤，您可以通过BFS填充parent level和level数组来逐步构建树结构。
伪代码
int [] parent = new int[n + 1]; int [] level = new int[n + 1]; Queue q = new Queue(); level[root.index] = 0; q.add(root); while(!q.isEmpty()){ Node node = q.dequeue(); parent[node.left.index] = node.index; parent[node.right.index] = node.index; level[node.left.index] = level[parent[node.left.index]] + 1; level[node.right.index] = level[parent[node.right.index]] + 1; q.add(node.left); q.add(node.right); }
这是一种方法，无需对树节点结构或任何其他内容进行任何更改。
-
在读取BFS队列时保持当前级别的
levelcounter = 0 -
同时保持nextlevel指针指向队列中第一个级别的节点。
-
Inital
nextlevel = null。 -
将新子项添加到队列时检查nextlevel指针是否为null，如果为null，则将其设置为当前子节点指针。
-
如果nextlevel等于最近删除的子节点的指针，则递增levelcounter并设置
nextlevel = null
levelcounter指示的级别是树中的节点级别。