Home > Mobile >  Binary Tree reverse level traversal
Binary Tree reverse level traversal

Time:07-11

enter image description here

my code:

void reversrorder(Btree B)
{
    if(!B) return;

    stack s = CreateStack();
    queue q = CreateQueue();
    
    int currentchildcount = 0, nextnumberofchildren = 0, height = 1;
    
    EnQueue(&q, B)
    
    while(Front(q, &B))
    {
        if(currentchildcount >= 0)
        {
            Push(&s, B);
            if(B->left)
            {
                EnQueue(&q, B->left);
                nextnumberofchildren  ;
            }
            if(B->right)
            {
                EnQueue(&q, B->right);
                nextnumberofchildren  ;
            }
            DeQueue(&q);
            currentchildcount--;
        }
        else
        {
            currentchildcount = nextnumberofchildren;
            nextnumberofchildren = 0;
            height  ;
        }
    }
    
    while(Top(s1, &B)
    {
        Pop(&s1);
        printf("%d ", B->data);
    }
}

I found a way to detect when I move to another level, and to get the height, but I couldn't figure out how I can get reverse level without reversing all the elements output was: 30 15 7 4 20 5 10

CodePudding user response:

I suppose you defined s1 as a stack (a typo?), but in essence you can solve this by first enqueuing the right child and then the left child. This way you generate a level order with all levels reversed. When at the end you iterate this in reversed order, the already reversed levels will come out in their "normal" left-to-right order.

  • Related