c - C中的级别顺序队列实现

Question

我理解了使用队列逐级访问二叉搜索树中节点的逻辑。但是我试图在 C 中实现，但我被卡住了，因为我不知道如何正确地将它们排入队列。从根开始，我可以创建一个队列，但之后如果我将根的子节点添加到队列中，我将丢失这些新节点的子节点，因为每次添加新节点时我都会修改队列中的连接。

我可以创建一种新的数据类型，它在链表队列中多了一个链接，应该可以。这里最好的方法是什么？

Answer 1

visit[ing] the nodes in a binary search tree level by level

有个名字:叫做树的“广度优先”遍历。从一个空队列开始，您将根节点入队，然后重复将队列中的第一个节点出队，以某种方式处理它，然后将该节点的所有子节点入队，直到没有更多节点入队。相对于该节点的其他处理，您应该准确地将节点的子节点入队的时间可能取决于您打算执行的具体处理，尤其是当它涉及在结构上修改树时。

只要每个节点的处理只能影响以当前节点为根的子树，就可以了。但是，如果您需要能够影响整个树的其他部分，那么广度优先遍历可能不适合您的任务。

你说

[I] don't know how to enqueue them properly. Starting with the root [I] can create a Queue but after that if [I] add the children of the root to the queue [I] will lose the children of those new nodes since [I] am modifying the connections in the Queue every time a add a new node.

这里的关键概念是队列中的成员资格和位置独立于树中的成员资格和位置。您可以通过向节点结构本身添加额外的链接，或通过为队列元素创建一个包含指向入队 BST 节点的指针的新结构来管理它。后者将树与队列分离，包括我在内的许多人认为对于大多数用途来说更可取。