Thread: Problem with binary search tree :(

  1. #1
    Unregistered
    Guest

    Problem with binary search tree :(

    Hi, sorry, I didn't use the search

    I prefer to get real answers from people, not look at already made answers. Anyway, here's the problem I'm having. My search tree isn't being created properly (or at all!). The problem lies with the 'searchPtr' in the 'sift' function. Anytime I use it for any comparison or assignment other than strcmp, the program bombs. I ran it through debug, and it looks like it's all OK, the value gets assigned just like it should, but it dies anyways!

    I will post the important sections of the program, this is actually a Windows dialog program though, so it's kinda long and I don't want to take too much space. Any help would be appreciated!

    (sorry for the lack of comments )

    Code:
    #include <windows.h>
    #include <tchar.h>
    #include <stdio.h>
    #include "phones.h"
    #include "resource.h"
    
    
    BOOL MainDialog_OnCommand(HWND, WORD, WORD, HWND);
    BOOL MainDialogProc(HWND, UINT, WPARAM, LPARAM);
    BOOL GetFileName(TCHAR *, int, HWND);
    void initialize (HWND);
    void sift(PTREE*);
    void printAll(PTREE*, HWND);
    
    TCHAR	szFilename[_MAX_PATH];
    HBITMAP	hBitmap;
    PTREE* index; //yeah yeah, it's global. Really the easiest (and best) way to do it.
    
    ....goes on with the windows stuff....
    
    void initialize(HWND hWnd)
    {
      PTREE* newNodePtr;
      FILE* ffp;
    
      //try to open the file,  Clean this up
      if( (ffp = fopen( szFilename, "rb")) == NULL )
      {
        //Create popup dialog error box
      }
    
      SetDlgItemText(hWnd, IDT_TEXT, "In init");
      
      index = (PTREE*) malloc (sizeof(PTREE));
      fread(index, sizeof(PREC), 1, ffp);
      index->left=NULL;
      index->right=NULL;
    
      newNodePtr = (PTREE*) malloc (sizeof(PTREE));
      fread(newNodePtr, sizeof(PREC), 1, ffp);
      newNodePtr->left=NULL;
      newNodePtr->right=NULL;
    
      while(!feof(ffp))
      {
        sift(newNodePtr);
        newNodePtr = (PTREE*) malloc (sizeof(PTREE));
        fread(newNodePtr, sizeof(PREC), 1, ffp);
        newNodePtr->left=NULL;
        newNodePtr->right=NULL;
      }
    
      free(newNodePtr);
      fclose(ffp);
    
      printAll(index, hWnd);
    
    }
    
    void sift(PTREE* newNodePtr)
    {
      PTREE* searchPtr, * attachHerePtr;
      int done = 0;
    
      searchPtr = index;
    
      while(searchPtr != NULL);
      {
    	  attachHerePtr = searchPtr;
    
        if(strcmp(newNodePtr->lname,searchPtr->lname)==-1)
          searchPtr = searchPtr->left;
        else
          searchPtr = searchPtr->right;
      }
      
      if(strcmp(newNodePtr->lname,searchPtr->lname)==-1)
    	attachHerePtr->left = newNodePtr;
      else
    	attachHerePtr->right = newNodePtr;
    
    }
    
    void printAll(PTREE* currentPtr, HWND hWnd)
    {
      static int index;//posibly use this for choice selection.
    
      if(currentPtr->left != NULL)
        printAll(currentPtr->left, hWnd);
    
      index = SendDlgItemMessage(hWnd, IDT_TEXT, LB_ADDSTRING, 0, (LPARAM)currentPtr->lname);
    
      if(currentPtr->right != NULL)
        printAll(currentPtr->right, hWnd);
    }

  2. #2
    Unregistered
    Guest
    Code:
    //your code
      if(strcmp(newNodePtr->lname,searchPtr->lname)==-1)
    	attachHerePtr->left = newNodePtr;
      else
    	attachHerePtr->right = newNodePtr;
    Maybe it should be:

    if (strcmp(newNodePtr->lname,attachHerePtr->lname) == -1)
    ...

  3. #3
    Unregistered
    Guest
    Note, this being after the while loop.

  4. #4
    Unregistered
    Guest
    Nope, but thanks for catching that! That probably would have been a bug in the future, bad copy-pasting on my part

    Here's more to the story. If I comment it out like so:

    Code:
    void sift(PTREE* newNodePtr)
    {
      PTREE* searchPtr, * attachHerePtr;
      
      searchPtr = index;
    
      //while(searchPtr != NULL);
      //{
    
        attachHerePtr = searchPtr;
    
       //if(strcmp(newNodePtr->lname,searchPtr->lname)==-1)
       //   searchPtr = searchPtr->left;
       // else
       //   searchPtr = searchPtr->right;
      //}
      
      if(strcmp(newNodePtr->lname,attachHerePtr->lname)==-1)
    	  attachHerePtr->left = newNodePtr;
      else
    	  attachHerePtr->right = newNodePtr;
    
    }
    Then it adds the left node and the right node perfectly, but of course can't go any farther than that. It, for some reason, doesn't like the while loop at all! I've been working on this for the last 3 days and just can't figure out what the heck is going wrong.

  5. #5
    Unregistered
    Guest
    Try:
    while(*searchPtr != NULL);

  6. #6
    Unregistered
    Guest
    BETTER YET:

    Take out the ::::::::::::::::'s lol

    Take out the exclamation mark right after the while. lol.

  7. #7
    Unregistered
    Guest
    Do:
    while (searchPtr != NULL)
    {
    ...
    }

    Instead of:
    while (searchPtr != NULL);
    {
    }

    And if that doesn't work than try:
    while (*searchPtr != NULL)
    {
    }

    Although that is a guess. I don't have a compiler to test with.

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Mmm, so many problems...
    The first problem is that your file reading loop will always result in at least one (perhaps two) garbage nodes in your tree.

    The logic here is
    Code:
    tree = NULL;
    while ( fread( temp, sizeof(PREC), 1, ffp) == 1 ) {
      // add temp to tree
    }
    2. while(searchPtr != NULL);
    This is a sure-fire way of making sure the code locks up - the ; means this loop will run forever, if the condition is initially true, since there is no way to make it false.

    3. read the manual about strcmp
    if(strcmp(newNodePtr->lname,attachHerePtr->lname)==-1)
    It says that strcmp returns a number <0 if s1 is before s2, it does not specifically state that it will return -1
    The only equality which strcmp returns is == 0, then the strings are identical.
    So,
    if(strcmp(newNodePtr->lname,attachHerePtr->lname) < 0 )

    It's probably worth testing this stuff as a separate small program, so you don't confuse GUI issues with tree issues.

  9. #9
    Unregistered
    Guest
    Thanks you guys. The problem was the stupid semi-colon at the end of the while loop. I can't believe I missed that

    Anyway, strcmp returns a -1 if less than, 0 if even, and 1 if greater. That's what my manual says at least, and it's the way I've used it for the last year.

    And yes, you're right. The file loop will always return a garbage node. But that node is never used, and is instatly freed right after the loop. Good for noticing it, but it's no problem really

  10. #10
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > Anyway, strcmp returns a -1 if less than, 0 if even, and 1 if greater. That's what my manual says at least
    Well it's wrong - it's being overly precise and it will cause you problems when you move to a more relaxed (yet still compliant) implementation.

    Picking one out at random
    http://www.mkssoftware.com/docs/man3/strcmp.3.asp

    And from the 'C' standard itself
    7.21.4.2 The strcmp function
    Synopsis
    1 #include <string.h>
    int strcmp(const char *s1, const char *s2);
    Description
    2 The strcmp function compares the string pointed to by s1 to the string pointed to by
    s2.
    Returns
    3 The strcmp function returns an integer greater than, equal to, or less than zero,
    accordingly as the string pointed to by s1 is greater than, equal to, or less than the string
    pointed to by s2.

  11. #11
    Unregistered
    Guest
    OK, cool. I will admit, the book I have on C is crappy at best. I'll go through and change the comparisons, no big deal. It's been working so far though, maybe i'm just lucky

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Tree - object instantiation problem
    By patricio2626 in forum C++ Programming
    Replies: 3
    Last Post: 11-14-2006, 02:11 AM
  2. binary tree token problem
    By OldSchool in forum C++ Programming
    Replies: 13
    Last Post: 05-28-2006, 10:42 PM
  3. Binary Search Tree
    By penance in forum C Programming
    Replies: 4
    Last Post: 08-05-2005, 05:35 PM
  4. Binary Search Tree, Inserting node
    By cheryl_li in forum C Programming
    Replies: 1
    Last Post: 09-13-2003, 03:53 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM