c - 遍历 n-Ary 树 Level Order

Question

让给定的结构:

// Struct to nAry tree
struct nNode {
  int val;                  // Some value (in future use a pointer to some data)
  struct nNode *next;       // Siblings of the same parent if next == NULL is the last
  struct nNode *prev;       // Siblings of same parent if prev == NULL is the first
  struct nNode *parent;     // Points to parent, if NULL is the root 
  struct nNode *children;   // Child node, other childs are found by moving next/prev
                            // if NULL is a leaf node
};

下面的代码应该给出关卡中的遍历

void nNode_traverse_levelOrder(struct nNode *node)
{
  struct nNode *child;
  struct nNode *sibling;
  struct nNode *head;

  struct QueueLL *queue;
  queue = newQueueLL();

  // Queue the root node
  enqueueLL(queue, node);

  while (! isQueueEmptyLL(queue)) {
    head = dequeueLL(queue);

    if(head) {
      visit(head);

      sibling = head->next;
      // Queue all brothers
      while(sibling) {
        enqueueLL(queue, sibling);
        sibling = sibling->next;
      }

      // Queue the children (there is only one)
      child = head->children;
      if (child) 
        enqueueLL(queue, child);
    }
  }
  destroyQueueLL(queue);
  queue = NULL;
}

给定树:

  /*                      1
   *            /---------|--------\
   *          2           3         4
   *        /   \                 /
   *      5       6              7
   */

返回

Node val: 1
Node val: 2
Node val: 3
Node val: 4
Node val: 5
Node val: 4
Node val: 7
Node val: 6
Node val: 7

但预期是 1 2 3 4 5 6 7。我已经仔细检查了 Pre、Pos 和 In order 遍历函数，它们都正确返回，如下所示:

PRE 1 2 _5 _6 _3 4 _7

POS _5 _6 2 _3 _7 4 1

IN _5 2 _6 1 _3 _7 4

想弄清楚是什么在我的职能中误导了我

Answer 1

当您访问一个节点时，您会将所有跟随它的兄弟节点加入队列。下一个 sibling 将再次排队其余的 sibling 。如果您有一个可以将元素添加到队列开头的操作，则可以在将子元素加入队列后使用该操作:

if (sibling) {
  pushLL(queue, sibling);
}

或者只是将 child 而不是 sibling 加入队列，这是通常的方法，并且可以缩短函数的长度:

void nNode_traverse_levelOrder(struct nNode* node) {
  struct QueueLL* queue = newQueueLL();

  enqueueLL(queue, node);

  while (!isQueueEmptyLL(queue)) {
    struct nNode* head = dequeueLL(queue);

    visit(head);

    for (struct nNode* child = head->children; child != NULL; child = child->next) {
      enqueueLL(queue, child);
    }
  }

  destroyQueueLL(queue);
}