Thread: Binary Trees

  1. #1
    Registered User
    Join Date
    Sep 2005
    Posts
    26

    Binary Trees

    Hi all,


    I'm trying to do a binary search and collect some stats from a text
    file in order to compare the processing times of this program (binary
    searching) versus an old program using linked lists. I'm totally new
    to binary searches by the way. Can anyone help me with the commented
    sections below? Much of the code such as functions and printfs has
    already been completed. Any help is greatly appreciated.


    Thanks,
    James


    Code:
     
    #include <stdio.h> 
    #include <malloc.h> 
    struct tnode {                  // specify the "shape" of a tnode structure ... 
            struct tnode *left;     // the left and right branch pointers 
            struct tnode *right; 
            int count;              // the word count as before 
            char *word;             // a pointer to the word 
    
    
    
    } *root;                        // declare the root pointer variable 
    
    
    struct tnode **tree_search(struct tnode **, char *); 
    void tree_stats(struct tnode *); 
    int get_word(char *); 
    
    int total_nodes, total_words, high; 
    struct tnode *most_frequent; 
    
    
    int main(int argc, char *argv[]) { 
            struct tnode **tpp; 
            char word_buff[100];    // the reusable word buffer 
            int i; 
            while(get_word(word_buff)) { 
                    tpp = tree_search(&root, word_buff); 
                    /****CODE TO ADD NEW NODES AND COUNT REPEATS *****/ 
    
    
            } 
            tree_stats(root); 
            printf("total_nodes %d\n", total_nodes); 
            printf("total_words %d\n", total_words); 
            if(most_frequent) 
                    printf("most frequent word <%s> count is %d\n", 
                            most_frequent->word, most_frequent->count); 
            for(i = 1; i < argc; i++) { 
                    tpp = tree_search(&root, argv[i]); 
                    if((*tpp) == NULL) 
                            printf("%s is NOT in the tree\n", argv[i]); 
                    else 
                            printf("<%s> count is %d\n", argv[i], (*tpp)->count); 
            } 
            return(0); 
    
    
    
    } 
    
    
    // binary tree search returning a pointer to the pointer leading to a 
    hit 
    struct tnode **tree_search(struct tnode **tpp, char *w) { 
            /***** CODE TO DO THE BINARY SRCH *****/ 
            return(tpp); 
    
    
    } 
    
    
    // gather stats to check tree correctness 
    void tree_stats(struct tnode *tp) { 
            /***** RECURSIVE CODE TO COLLECT ALL OF THE STATISTICS *****/ 
    
    
    } 
    
    
    #include <ctype.h> 
    /* Leave this routine EXACTLY as it stands */ 
    int get_word(char *s) { 
            int c; 
            do { 
                    c = getchar(); 
                    if(c == EOF) 
                            return(0); 
            } while(!isalpha(c) && !isdigit(c)); 
            do { 
                    if(isupper(c)) 
                            c = tolower(c); 
                    *s++ = c; 
                    c = getchar(); 
            } while(isalpha(c) || isdigit(c)); 
            *s = 0; 
            return(1); 
    
    
    }

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    We're not going to do a "fill in the blanks" homework problem for you. If you really want to learn more about binary trees, search for information on them. You could start by reading the entries in the FAQ section of this forum. Once you're done with that, if you still can't get it, try searching the forum. If you still can't get it after that, consider your search engine of choice.

    Also, actually make an attempt, rather than just pasting in your assignment.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    Eew.

    >#include <malloc.h>
    I wonder how this ancient header is still known by beginners when it hasn't been valid for, what, almost 20 years now? Use stdlib.h.

    >struct tnode **tree_search(struct tnode **, char *);
    You're using an unnecessary level of indirection and making your life harder because of it. The same effect can be had with only a pointer to a node:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct jsw_node {
      int data;
      struct jsw_node *link[2];
    };
    
    static struct jsw_node *new_node ( int data )
    {
      struct jsw_node *rn = malloc ( sizeof *rn );
    
      if ( rn != NULL ) {
        rn->data = data;
        rn->link[0] = NULL;
        rn->link[1] = NULL;
      }
    
      return rn;
    }
    
    struct jsw_node *jsw_insert ( struct jsw_node *root, int data )
    {
      if ( root == NULL )
        root = new_node ( data );
      else {
        struct jsw_node *it;
        int dir;
    
        for ( it = root; ; it = it->link[dir] ) {
          dir = it->data < data;
          if ( it->link[dir] == NULL )
            break;
        }
    
        it->link[dir] = new_node ( data );
      }
    
      return root;
    }
    
    void jsw_structure ( struct jsw_node *root, int level )
    {
      int i;
    
      if ( root == NULL ) {
        for ( i = 0; i < level; i++ )
          putchar ( '\t' );
        puts ( "~" );
      }
      else {
        jsw_structure ( root->link[1], level + 1 );
        for ( i = 0; i < level; i++ )
          putchar ( '\t' );
        printf ( "%d\n", root->data );
        jsw_structure ( root->link[0], level + 1 );
      }
    }
    
    int main ( void )
    {
      struct jsw_node *root = NULL;
      int i;
    
      for ( i = 0; i < 10; i++ )
        root = jsw_insert ( root, rand() % 100 );
      jsw_structure ( root, 0 );
    
      return 0;
    }
    My best code is written with the delete key.

  4. #4
    Registered User
    Join Date
    Sep 2005
    Posts
    26
    Hi guys,

    Thanks for the help so far. My template is from a book I'm self-teaching myself C from for a job switch. I'm not asking for anyone to do it for me, just help or tips that will help guide me along the way.

    Thanks,
    James

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >My template is from a book I'm self-teaching myself C from for a job switch.
    Get another book. I'd recommend "The C Programming Language" by Brian Kernighan and Dennis Ritchie, as well as Pointers on C by Kenneth Reek.
    My best code is written with the delete key.

  6. #6
    Registered User
    Join Date
    Sep 2005
    Posts
    26
    Hi,


    Am I on the right path in the section of the code that adds new nodes?
    I'm not finished, but trying to make an attempt. It's under the
    /****CODE TO ADD NEW NODES AND COUNT REPEATS *****/ section. I'm
    pretty sure that it's supposed to check if it's null and if so,
    allocates memory for a new node. Syntax is probably wrong, but was
    hoping for some input.


    Thanks,
    James


    Code:
     
    #include <stdio.h> 
    #include <malloc.h> 
    struct tnode {                  // specify the "shape" of a tnode 
    structure ... 
            struct tnode *left;     // the left and right branch pointers 
            struct tnode *right; 
            int count;              // the word count as before 
            char *word;             // a pointer to the word 
    
    
    
    } *root;                        // declare the root pointer variable 
    
    
    struct tnode **tree_search(struct tnode **, char *); 
    void tree_stats(struct tnode *); 
    int get_word(char *); 
    
    int total_nodes, total_words, high; 
    struct tnode *most_frequent; 
    
    
    int main(int argc, char *argv[]) { 
            struct tnode **tpp; 
            char word_buff[100];    // the reusable word buffer 
            int i; 
            while(get_word(word_buff)) { 
                    tpp = tree_search(&root, word_buff); 
                    /****CODE TO ADD NEW NODES AND COUNT REPEATS *****/ 
                   ///new code below here 
                   if(root==NULL) 
                            if(*tpp==NULL){ 
                                    tpp=malloc(sizeof(struct tnode)); 
                                    tpp->word = strdup(word_buff); 
                                    tpp->*left = NULL; 
                                    tpp->*right = NULL; 
                            } 
                    else statement here if there's a node there, increments 
                    count I think, not sure which variables to use 
    
    
            }

  7. #7
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Am I on the right path in the section of the code that adds new nodes?
    No, you're not. Stop using that silly double pointer and study the code I posted. Binary search trees can be as easy or as hard as you make them, and you're making them harder than they should be.
    My best code is written with the delete key.

  8. #8
    Registered User
    Join Date
    Sep 2005
    Posts
    26
    Hi everyone,

    Just wanted to say thanks for the help on this one. FINALLY got it working.

    Take care,
    James

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Converting From Binary Tree to Threaded Binary Trees
    By elton_fan in forum C Programming
    Replies: 15
    Last Post: 11-08-2007, 11:41 PM
  2. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 02:12 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM