Traverse arbre n-Ary Niveau ordre

Question

Que la structure donnée par:

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

Le code ci-dessous devrait donner la Traverse au niveau

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

Compte tenu de l'arbre:

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

Renvoie

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 

Mais attendu est 1 2 3 4 5 6 7. J'ai revérifié avec pré, Pos et dans les fonctions transversales de commande et tous les renvoie correctement, comme ci-dessous:

PRE 1 2 _5 _6 _3 4 _7 

POS _5 _6 2 _3 _7 4 1 

IN _5 2 _6 1 _3 _7 4 

Vous cherchez à comprendre ce que peut me tromper dans ma fonction

Answer 1

Lorsque vous visitez un nœud, vous mettez en file d'attente tous les frères et sœurs qui le suivent. Le prochain frère mettra en file d'attente le reste des frères et soeurs. Si vous avez une opération qui peut ajouter un élément au début de la file d'attente, vous pouvez l'utiliser après mise en attente de l'enfant:

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

Ou seulement les enfants enqueue au lieu de frères et sœurs, ce qui est de la manière habituelle et marques pour une beaucoup plus courte fonction: (! isQueueEmptyLL (en attente))

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