1

让结构由下式给出：

// 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

想弄清楚在我的职能中可能会误导我的事情

4

1 回答 1

2

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

if (sibling) {
  pushLL(queue, 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);
}
于 2017-06-25T23:19:58.080 回答