遍历 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
   */

它returns

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 遍历函数，它们都 returns 正确，如下所示：

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

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

入队

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

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

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);
}

遍历 n-Ary 树 Level Order

Traverse n-Ary tree Level Order

c

algorithm

tree

traversal

n-ary-tree