Thread: Searching a Biinary Search Tree

So I have a Binary search tree where each node holds a struct called WORD which contains three fields: a dynamically allocated string (word), an int indicating the number of times the word is found in a text file (count) and an int indicating the number of times it was searched by the user (search_count).

I am trying to complete a search function whereby the user inputs an integer and all words that appear that amount of times are printed to the screen and continues to do so until the user enters -1.

The problem I am having is when I try to run the loop to do this..
It prints the first result indefinitely..

Code:

void searchFreq (BST_TREE *list)
{
    WORD target, *wordPtr;

    printf("Enter a frequency, enter -1 to exit: ");
    scanf("%d", &target.count);
    while(target.count != -1)
    {
        wordPtr = (WORD*)BST_Retrieve (list, &target);
        if(!wordPtr)
            printf("No words with such a frequency were found\n");
        else{
            while(wordPtr != NULL){
                wordPtr->search_count++;
                printf("Word: %s\n",    wordPtr->word);
                printf("Frequency:  %d\n", wordPtr->count);
                printf("Search count: %d\n", wordPtr->search_count);
                wordPtr = (WORD*)BST_Retrieve (list, wordPtr);
            }
        }
        printf("Enter a frequency, enter -1 to exit: ");
        scanf("%d", &target.count);
    }
}

Any and all feedback is appreciated

What prevents BST_Retrieve from simply returning the first node it finds that matches, indefinitely? You always start your search from the root of the tree.

How could I get it to continue traversing from the point where it left off? the parameter only supports a tree header structure, not a node from the tree

You could do two things. The easy way is to start new searches after you find the initial match on both of the matching node's children. Keep going in this way until you find leaves on both sides of the tree. The other way to do it would be to re-orient the tree around the frequency of the words, making the frequency the key. But you could have multiple words as values for each of the keys in the tree. Then you would have to just traverse the tree. It really depends on what you think you can/want to do.

There are two trees, both of which are pointing to the same data.
The key of the tree in question already is the frequency.
I ended up solving it by using a breadth first traversal function I came up with, the only difference being that I added a parameter and used the compare function from the header structure to determine weather or not to process the data in the node being traversed:

Code:

void BST_BreadthFind (BST_TREE* tree, void * dataPtr,
    void (*process) (void* dataPtr))
{
    QUEUE *q;
    NODE *traverse, *newPtr;

    newPtr = (NODE*)malloc(sizeof(NODE));
    if (!newPtr)
        return;

    newPtr->right   = NULL;
    newPtr->left    = NULL;
    newPtr->dataPtr = dataPtr;

    if(!tree->root)
        return;
    q = createQueue();
    enqueue(q, tree->root);
    while(!emptyQueue(q)){
        dequeue(q, (void**)&traverse);
        if(tree->compare(newPtr->dataPtr, traverse->dataPtr) == 0)
            process(traverse->dataPtr);
        if(traverse->left)
            enqueue(q, traverse->left);
        if(traverse->right)
            enqueue(q, traverse->right);
    }
    destroyQueue(q);
    free(newPtr);
    return;
}

So my search function ended up looking like this:'

Code:

void searchFreq (BST_TREE *list)
{
    WORD target, *wordPtr;

    printf("\nEnter a frequency, enter -1 to exit: ");
    target.count = scanInt();
    while(target.count != -1)
    {
        wordPtr = (WORD*)BST_Retrieve (list, &target);
        if(!wordPtr)
            printf("No words with a frequency of %d were found\n", target.count);
        else
            BST_BreadthFind(list, &target, printResult);
        printf("\nEnter a frequency, enter -1 to exit: ");
        target.count = scanInt();
    }
}//searchFreq