トラバースN進ツリーレベルの注文

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 

何を把握するために探し

PRE 1 2 _5 _6 _3 4 _7 

POS _5 _6 2 _3 _7 4 1 

IN _5 2 _6 1 _3 _7 4 

：

しかし期待は、私は二重の前、順位で注文トラバース機能でチェックしていると、それらのすべてが以下のように、正常に戻ります1 2 3 4 5 6 7です。私の機能で私を誤解させる可能性があります

Answer 1

ノードにアクセスすると、それに続くすべての兄弟をエンキューします。次の兄弟は残りの兄弟を再度エンキューします。代わりに、兄弟の

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