Thread: Question about binary trees and files

  1. #1
    Registered User
    Join Date
    Oct 2004
    Posts
    27

    Question about binary trees and files

    Ive got an assignment to do over the weekend in c. Firstly the assisgment is to create a game which asks the user a question from there they can pick yes of no. When the user picks a person and answers the questions the program will determin who that person is but when the program cant find a match the program will ask the user for that person and an associating question to distingus them. The data is meant to be in a binary tree from a file so that when the program is run it will remember the persons added to the file.


    So for the last few hours ive decided that my file will be laid out as so:
    Code:
    1 Are you Female?
    2 //space for another question going down the yes side
    3 //space for another question going down the no side
    etc

    The only program that i can invisage now is how can one search through the file to find the corresponding number to the next question it should ask? and then print that line to the user to get a reply from. Ive gone though the faq on files but could not make sense of the fseek function that i need to use


    Any help would be greatly needed
    Always posting problems

    Always needing help

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    I'd read the whole file into a struct such as
    Code:
    struct qa {
      char *question;
      struct qa *false_answer;
      struct qa *true_answer;
    } qa;
    Of course, the real problem is working out from the file whether the 2nd question is relevant to the "true" path or the "false" path.
    1 Are you Female?
    2 //space for another question going down the yes side
    3 //space for another question going down the no side
    1 Are you a student?
    2 //space for another question going down the yes side
    3 //space for another question going down the no side

  3. #3
    Registered User
    Join Date
    Oct 2004
    Posts
    27
    the way i was going to solve that was
    Code:
    
    1 Are you Female?
    2 //space for another question going down the yes side
    3 //space for another question going down the no side
    4 //Another question for the yes side of 2
    5 //Another question for the no side of 2
    6 //Another question for the yes side of 3
    7 //Another question for the no side of 3
    
    if got this format of another website so when the user answers yes to question 2 the next question line will be got be:


    Question+Question i.e. 2+2 = 4

    though if the user enters no then its:
    Question + Question + 1 i.e. 2+2+1 = 5



    etc
    Last edited by satory; 03-03-2006 at 10:17 AM.
    Always posting problems

    Always needing help

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    Ok, so just read a question and allocate nodes as appropriate

  5. #5
    Registered User
    Join Date
    Oct 2004
    Posts
    27
    though what im looking for is a way at the moment to search through the file and pull out that line with the approiate question. the indexing of the questions will be used to get the line needed so if i want question number 4 i'll search the file for the instance of the number four
    Always posting problems

    Always needing help

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    In order to be able to seek to a specific line, you need to read the whole file first and produce an index of where each line starts.
    ie, a loop calling fgets() and ftell().

    When you need to goto a line, you can find a value to pass to fseek(), then call fgets() to read that line.

  7. #7
    Registered User
    Join Date
    Oct 2004
    Posts
    27
    so im im just writing up the code now but ive come up against a anoher same problem

    Code:
    struct treeNode { 
       struct treeNode *yesPtr;  /* pointer to yes subtree */
       int num; /* node value */
       char question[50];
       struct treeNode *noPtr; /* pointer to no subtree */
    }; /* end structure treeNode */
    
    
    typedef struct treeNode TreeNode; /* synonym for struct treeNode */
    typedef TreeNode *TreeNodePtr; /* synonym for TreeNode* */
    
    
    void insertNode(TreeNodePtr *treePtr, char text[], int value);
    void NewGame ();
    void Continue ();
    void inOrder( TreeNodePtr treePtr );
    
    int main (void)
    {
    
        int choice;
        do
        {
              printf("Please enter your choice: ");
              scanf("%i",&choice);
        }
        while ((choice <= 0) && (choice >=4)); 
        
        if (choice == 1)
        {
             NewGame();
        }
        else if (choice == 2)
        {
             Continue();    
        }
        else if (choice == 3)
        {
             return 0; 
        }
        
        scanf ("%i",&choice);
        return 0;
    }
    
    void NewGame ()
    {
         char Filename[50];
         FILE *in;
         TreeNodePtr rootPtr = NULL; /* tree initially empty */
         int Qnum;
         char Qtext[50] = "Are You Female";
         
         printf ("This is the new game function\n\n");
         printf ("Please provide the new file name: ");
         scanf ("%s",Filename);
         printf ("\n\n%s",Filename);
         
         in = fopen(Filename,"rwb");
         
         if ( in == NULL ) 
         {
              perror ( "Unable to open the file" );
              exit ( EXIT_FAILURE );
         }
         else
         {
             Qnum = 1;
             
             insertNode(&rootPtr, Qtext[50], Qnum);        
         }
         
    }
    void insertNode( TreeNodePtr *treePtr, char text[], int value )
    {
         /* if tree is empty */
       if ( *treePtr == NULL ) {   
          *treePtr = malloc( sizeof( TreeNode ) );
    
          /* if memory was allocated then assign data */
          if ( *treePtr != NULL ) { 
             ( *treePtr )->num = value;
             ( *treePtr )->question[50] = text[50]; 
             ( *treePtr )->yesPtr = NULL;
             ( *treePtr )->noPtr = NULL;
          } /* end if */
          else {
             printf( "%i not inserted. No memory available.\n", value );
          } /* end else */
    
       } /* end if */
       else { /* tree is not empty */
    
          /* data to insert is less than data in current node */
          if ( value < ( *treePtr )->num ) {
             insertNode( &( ( *treePtr )->yesPtr ), text[50], value );
          } /* end if */
    
          /* data to insert is greater than data in current node */
          else if ( value > ( *treePtr )->num ) {
             insertNode( &( ( *treePtr )->noPtr ), text[50], value );
          } /* end else if */
          else { /* duplicate data value ignored */
             printf( "dup" );
          } /* end else */
    
       } /* end else */   
    }
         
    void Continue()
    {
         printf ("This is the continue game function");
    }
    im getting errors when i call the insertnode function its to do with the parameters and the string useage im using

    can anyone help me


    ps i have left some bits out but they are working so ive not included them ....... for now
    Always posting problems

    Always needing help

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    > insertNode(&rootPtr, Qtext[50], Qnum);
    To pass an array, just use it's name
    insertNode(&rootPtr, Qtext, Qnum);

    > ( *treePtr )->question[50] = text[50];
    To copy an array of chars, use strcpy
    strcpy ( ( *treePtr )->question, text );

  9. #9
    Registered User
    Join Date
    Oct 2004
    Posts
    27

    Post

    Cheers for the help above but can you see if im on the right path for the idea you gave earlier


    Quote Originally Posted by Salem
    In order to be able to seek to a specific line, you need to read the whole file first and produce an index of where each line starts.
    ie, a loop calling fgets() and ftell().

    When you need to goto a line, you can find a value to pass to fseek(), then call fgets() to read that line.

    Code:
    while ( !feof(in))
    {
             fgets(num,50,in);
             offset = ftell(in);
    	pos[value] = offset;
    	value++;
    }
    ret = fseek(in, pos[Qnum], SEEK_SET);
    fgets(num, ret, in);
    where in is the file pointer. num is a char = to an int, ret and pos are integers
    Last edited by satory; 03-06-2006 at 06:28 AM.
    Always posting problems

    Always needing help

  10. #10
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    Code:
    char num[50];
    int value = 0;
    long pos[1000];
    while ( value < 1000 && fgets(num,sizeof num,in) ) {
      pos[value++] = ftell( in );
    }
    Seeking and reading a line is as you've got it

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. arrays vs lists? And containers in general!
    By clegs in forum C++ Programming
    Replies: 22
    Last Post: 12-03-2007, 02:02 PM
  2. Saving trees in files
    By Magos in forum C++ Programming
    Replies: 19
    Last Post: 08-29-2004, 04:08 PM
  3. I Need To Know Some Things That I Can Put Into A Batch File
    By TheRealNapster in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 10-20-2003, 08:12 PM
  4. Dos commands hehe
    By Carp in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 01-17-2003, 02:51 PM
  5. binary search trees in C
    By seeks in forum C Programming
    Replies: 1
    Last Post: 02-18-2002, 04:22 AM