treemanagement.c

treemanagement.c

/* File: treemanagement.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct tnode *Treeptr;

typedef struct tnode {
  char *word;
  Treeptr left;
  Treeptr right;
} Treenode;

Treeptr addtree(Treeptr, char *);
void treeprint(Treeptr, int);
void nodesprint(Treeptr);
int treedepth(Treeptr);
int treesearch(Treeptr, char *);

int main(int argc, char *argv[])
{ Treeptr p;
  char buf[80];
  p = NULL;                              /* Initialize binary tree */
  while (scanf("%s", buf) != EOF)         /* Read words from input */
    p = addtree(p, buf);          /* and insert them into the tree */
  printf("Tree is:\n"),
  treeprint(p, 0);                 /* Kind of tree pretty printing */
  printf("\nNodes are:\n");
  nodesprint(p);         /* Print tree nodes in alphabetical order */
  printf("\n\nTree depth is %d\n", treedepth(p));
                                /* Compute and print depth of tree */
  printf("\n");
  while (--argc) {                            /* For each argument */
    argv++;       /* check whether it coincides with any tree node */
    printf("%s found %s\n",
           (treesearch(p, *argv)) ? "   " : "not", *argv);
  }
  return 0;
}

Treeptr addtree(Treeptr p, char *w)   /* Insert word w into tree p */
{ int cond;
  if (p == NULL) {                             /* If tree is empty */
    p = malloc(sizeof(Treenode));   /* Allocate space for new node */
                                    /* Allocate space to copy word */
    p->word = malloc((strlen(w)+1) * sizeof(char));
    strcpy(p->word, w);                /* Copy word w to tree node */
    p->left = NULL;           /* Left subtree of new node is empty */
    p->right = NULL;         /* Right subtree of new node is empty */
  }
  else if ((cond = strcmp(w, p->word)) < 0)
                      /* Does word w precede word of current node? */
    p->left = addtree(p->left, w);
                            /* If yes, insert it into left subtree */
  else if (cond > 0)       /* Does it follow word of current node? */
    p->right = addtree(p->right, w);
                           /* If yes, insert it into right subtree */
  /* If it is the same with word of current node, do not insert it */
  return p;                                         /* Return tree */
}

void treeprint(Treeptr p, int ident)          /* Pretty print tree */
{ int i;
  if (p != NULL) {                         /* If tree is not empty */
    treeprint(p->right, ident+4);
                /* Print right subtree 4 places right of root node */
    for (i=0 ; i < ident ; i++)
      printf(" ");                    /* Take care for indentation */
    printf("%s\n", p->word);                    /* Print root node */
    treeprint(p->left, ident+4);
                 /* Print left subtree 4 places right of root node */
  }
}

void nodesprint(Treeptr p)                     /* Print tree nodes */
{ if (p != NULL) {                         /* If tree is not empty */
    nodesprint(p->left);                     /* Print left subtree */
    printf("%s ", p->word);                     /* Print root node */
    nodesprint(p->right);                   /* Print right subtree */
  }
}

int treedepth(Treeptr p)                /* Compute depth of tree p */
{ int n1, n2;
  if (p == NULL)                       /* Depth of empty tree is 0 */
    return 0;
  n1 = treedepth(p->left);        /* Compute depth of left subtree */
  n2 = treedepth(p->right);      /* Compute depth of right subtree */
  return (n1 > n2) ? n1+1 : n2+1;
     /* Return maximun of depths of left and right subtrees plus 1 */
}

int treesearch(Treeptr p, char *w)
                              /* Check whether word w is in tree p */
{ int cond;
  if (p == NULL)                               /* If tree is empty */
    return 0;                               /* We didn't find word */
  if ((cond = strcmp(w, p->word)) == 0)
                   /* Word w is the same with word of current node */
    return 1;
  else if (cond < 0)         /* If w precedes word of current node */
    return treesearch(p->left, w);          /* Search left suftree */
  else                                                /* Otherwise */
    return treesearch(p->right, w);        /* search right subtree */
}

This code comes from ip course of DIT, Athens (Πληροφορική & Τηλεπικοινωνίες, ΕΚΠΑ)

treemanagementINT.c

I have modified the code above to host integers, instead of strings. Moreover, I have written a function to determine if the binary tree is ordered, i.e. a BST.

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define max(x, y) (((x) > (y)) ? (x) : (y))
#define min(x, y) (((x) < (y)) ? (x) : (y))

typedef struct tnode *Treeptr;

typedef struct tnode {
  int value;
  Treeptr left;
  Treeptr right;
} Treenode;

Treeptr addtree(Treeptr, int);
void treeprint(Treeptr, int);
void nodesprint(Treeptr);
int treedepth(Treeptr);

int fun(Treeptr p, int* ap, int* bp);

int ordtree(Treeptr p) {
  int a, b;
  return (p == NULL || fun(p, &a, &b));
}

int fun(Treeptr p, int * ap, int * bp) {
  int a, b;
  // Is 'p' a leaf?
  if (p->left == NULL && p->right == NULL) {
    *ap = p->value;
    *bp = p->value; return 1; // Gap C
  }

  // Does 'p' have only a left child?
  if (p->right == NULL) {
    *bp = p->value;
    return (fun(p->left, ap, &b) && p->value > b); // Gap D
  }

  // Does 'p' have only a right child?
  if (p->left == NULL) {
    *ap = p->value;
    return (fun(p->right, &a, bp) && p->value < a); // Gap G
  }

  // 'p' has two children
  return (fun(p->right, &a, bp) && fun(p->left, ap, &b) && a > p->value && p->value > b); // Gap H
}

int main(int argc, char *argv[]) {
  Treeptr p;
  int v;
  p = NULL; /* Initialize binary tree */
  while (scanf("%d", &v)) { /* Read numbers from input */
    if (v == -1)                     // if user typed -1
      break;                     // stop reading from input
    p = addtree(p, v); /* and insert them into the tree */
  }

  printf("Tree is:\n"), treeprint(p, 0); /* Kind of tree pretty printing */
  printf("\nNodes are:\n");
  nodesprint(p); /* Print tree nodes in alphabetical order */
  printf("\n\nTree depth is %d\n", treedepth(p));
  /* Compute and print depth of tree */
  printf("\n");

  printf("Is ordered? %d\n", ordtree(p));

  return 0;
}

Treeptr addtree(Treeptr p, int v) /* Insert number v into tree p */
{
  if (p == NULL) { /* If tree is empty */
    p = malloc(sizeof(Treenode)); /* Allocate space for new node */
    p->value = v; /* Copy number  to tree node */
    p->left = NULL; /* Left subtree of new node is empty */
    p->right = NULL; /* Right subtree of new node is empty */
  } else if (v < p->value)
    /* Does number v precede number of current node? */
    p->left = addtree(p->left, v);
  /* If yes, insert it into left subtree */
  else if (v > p->value) /* Does it follow number of current node? */
    p->right = addtree(p->right, v);
  /* If yes, insert it into right subtree */
  /* If it is the same with number of current node, do not insert it */
  return p; /* Return tree */
}

void treeprint(Treeptr p, int ident) /* Pretty print tree */
{
  int i;
  if (p != NULL) { /* If tree is not empty */
    treeprint(p->right, ident + 4);
    /* Print right subtree 4 places right of root node */
    for (i = 0; i < ident; i++)
      printf(" "); /* Take care for indentation */
    printf("%d\n", p->value); /* Print root node */
    treeprint(p->left, ident + 4);
    /* Print left subtree 4 places right of root node */
  }
}

void nodesprint(Treeptr p) /* Print tree nodes */
{
  if (p != NULL) { /* If tree is not empty */
    nodesprint(p->left); /* Print left subtree */
    printf("%d ", p->value); /* Print root node */
    nodesprint(p->right); /* Print right subtree */
  }
}

int treedepth(Treeptr p) /* Compute depth of tree p */
{
  int n1, n2;
  if (p == NULL) /* Depth of empty tree is 0 */
    return 0;
  n1 = treedepth(p->left); /* Compute depth of left subtree */
  n2 = treedepth(p->right); /* Compute depth of right subtree */
  return (n1 > n2) ? n1 + 1 : n2 + 1;
  /* Return maximun of depths of left and right subtrees plus 1 */
}

Have questions about this code? Comments? Did you find a bug? Let me know!😀
Page created by G. (George) Samaras (DIT)

4 thoughts on “treemanagement.c

  1. Pingback: Functions Max in binary tree

  2. Pingback: Sum of depths in a binary tree.

  3. Pingback: Quadtrees

  4. Pingback: Function to determine if a tree is sorted (i.e. BST)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s