Searching a Biinary Search Tree

This is a discussion on Searching a Biinary Search Tree within the C Programming forums, part of the General Programming Boards category; So I have a Binary search tree where each node holds a struct called WORD which contains three fields: a ...

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    46

    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

  2. #2
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,762
    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.

  3. #3
    Registered User
    Join Date
    Nov 2011
    Posts
    46
    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

  4. #4
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,762
    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.

  5. #5
    Registered User
    Join Date
    Nov 2011
    Posts
    46
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Array based Binary search tree- Searching
    By mrsirpoopsalot in forum C++ Programming
    Replies: 1
    Last Post: 12-07-2009, 12:53 AM
  2. a searching tree
    By lindaonline15 in forum C++ Programming
    Replies: 2
    Last Post: 10-15-2008, 07:06 AM
  3. Searching a binary search tree - doesn't work
    By Ariod in forum C Programming
    Replies: 1
    Last Post: 08-11-2005, 04:53 PM
  4. Search Engine - Binary Search Tree
    By Gecko2099 in forum C Programming
    Replies: 9
    Last Post: 04-17-2005, 03:56 PM
  5. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 05:15 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21