Making a function that counts number of elements in PriorityQueue in C

Question

TASK:

I am working on a homework for my Structure and Algorithms college class. The task is to implement Priority Queue in C using the heap and form the main so it can support operations such as:

INSERT s (inserts string s in a Priority Queue)
DELETE (deletes the element with the lowest priority)
NUMBER (returns number of elements in a Priority Queue)

We should also print out preorder of the Priority Queue every time we write an operation in the main. We can assume that the heap is implemented with the pointers. So I implemented it in structure that looks like this:

typedef char* elementtype;

typedef struct celltag {
    elementtype zapis;
    struct celltag *left, *right, *parent;
}   celltype;

typedef celltype* node;
typedef celltype* PriorityQueue;

I also implemented following functions:

void PrMakeNull(PriorityQueue *Ap)
int PrEmpty(PriorityQueue A)
void PrInsert(elementtype x, PriorityQueue *Ap)
elementtype PrDeleteMin(PriorityQueue *Ap)
void Preorder(PriorityQueue A)

QUESTION:
I should implement "number function" with the header like this:

int Number(PriorityQueue P)

The function should not change the Priority Queue A after calling Number(A). Also, the function should be independent on Priority Queue implementation. (I think that means I should only use PrMakeNull, PrEmpty, PrInsert, PrDeleteMin). Is that even possible? How could I do it? How should it look like?

WHAT HAVE I TRIED:
1)

//This one is independent on Priority Queue implementation but destroys the Priority Queue. 
int Number(PriorityQueue P){
    PriorityQueue S;
    PrMakeNull(&S);
    int counter=0;
    while(!PrEmpty(P))
    {
        PrInsert(PrDeleteMin(&P), &S);
        counter++;
    }
    while(!PrEmpty(S))
    {
        PrInsert(PrDeleteMin(&S), &P);
    }
    return counter;
}

2)

//This one is dependent on Priority Queue implementation but doesn't destroy the Priority Queue. 
int Number(PriorityQueue A){
    int returning_number=1;
    if (A == NULL)
        return 0;
    if(A->left!=NULL)
        returning_number+=Number(A->left);
    if(A->right!=NULL)
        returning_number+=Number(A->right);
    return returning_number;
}

Answer 1

You can solve this with a recursive algorithm that does not depend on function you list. The code could be like this :

int Number(PriorityQueue A)
{
    if(!A) return 0;

    return 1 + Number(A->left) + Number(A->right);
}

This is the best way to solve this for my opinion.

if you have some trouble on recursion i leave you a useful link:

recursion

Edit:

I don't think there is a possible to abstract from the struct of priority queue this because the implementation of PrEmpty, PrInsert, PrDeleteMin, and Preorder already depends on the struct of priority queue. So why search for an implementation that depends only on these function? Also to be generic you can define another function that search for an element without delete them and implement it at the same level of the above function, or better a simple iterator over the priority queue.