binarytree.c

/* implementation and operations with binary trees */

 /* pointer arithmetics:
  *
  * push(pointer, v) INDICATES *(pointer++) = v
  * pop(pointer) INDICATES *(--pointer)
  * (*++v)[0] INDICATES (**++v)
  *           INDICATES first char in v
  *           INDICATES name of string/vector v
  * likewise, *v[0] INDICATES **v
  *       and *v[n] INDICATES **(v + n)
  * returntype (*funct)(args) INDICATES a function funct with arguments args which returns...
  * char **argv INDICATES pointer to char pointer
  * int(*v)[len] INDICATES pointer "v" to a vector of "len" int elements
  * int *v[len] INDICATES vector "v" of "len" pointers to int elements
  * void *funct() INDICATES function "funct" that returns a pointer-to-void
  * void (*funct)() INDICATES pointer to a function "funct" that returns void
  *
  */

 /* useful characters: [] # */

 # include <stdio.h>
 # include <ctype.h>
 # include <string.h>

 # define MAXL 100

 /* binary tree node */

 struct node {
   char * data;
   int value;
   struct node * left;
   struct node * right;
 };

 /* node manipulation */

 struct node * newtree(struct node * n, char * data);
 void print(struct node * n);
 int getvalue(char * data, int value);

 /* main */

 int main(int argc, char * argv[])
    {
     struct node * root; // binary tree root
     char data[MAXL];
     root = NULL;

     while(getword(data, MAXL) != EOF) // extracts data until the end of file...
    root = newtree(root, data); // ...and parses it into a new tree node
     print(root); // prints the tree
     return 0;
    }

 /* creates a new node and appends it to the current tree, generating a new subtree */

 struct node * newtree(struct node * n, char * data)
    {
     if(n = NULL) // case 1: the tree has just been created
    {
    n = (struct node *)malloc(sizeof(struct node)); // IMPORTANT: creates a new node by allocating it in memory directly
    n->data = strdup(data); // copies the data into the new node
    n->value = 1;
    n->left = n->right = NULL;
    }
     else // case 2: the tree is already present and needs a subtree
    {
     if(strcmp(data, n->data) == 0) // word repeated
        n->value++;
     else if(strcmp(data, n->data) < 0) // adds to left subtree
        n->left = newtree(n->left, data);
     else // adds to right subtree
        n->right = newtree(n->right, data);
    }
    return n;
    }

 /* prints the binary tree */

 void print(struct node * n)
    {
     if(n != NULL)
    {
     print(n->left);
     printf("Value: %d Data: %s\n", n->data);
     print(n->right);
    }
    }