A project for Data Structures by Dave Schoeffler during the Fall 2011 semester.

This project was begun on December 14th and was completed on December 14th.

The purpose of this project is to explore the nature of binary trees through their use in various functions. This will require a knowledge linked lists and pointers.

In order to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved:

• understand functions
• understand pointers
• understand structs
• understand malloc()
• ability to create a linked data structure
• ability to create a binary tree data structure

The point of this project is to implement a tree that will store characters.

Binary trees are very useful in storing data because they allow you to search for data very quickly. A more detailed explanation of Binary Trees can be found here → http://en.wikipedia.org/wiki/Binary_search_tree

To better utilize the functionality of the trees we've been studying in class, a personal implementation for use as a library will be undertaken for use in other projects and activities this semester.

Working from the class example, a library implementation will be created which has the following functions:

• insert: adds a node to the binary tree. If no tree exists it will create one
• display: display the values of the tree in lexicographical order

• pointers: pointers are at the heart of dynamic structures.
• linked lists: this code is going to implement linked lists.
• doubly linked lists: not only is the code implementing a linked list, it is implementing doubly linked lists.
• libraries: this code will be part of a library that can be reused in other projects
• trees: this code will implement the use of trees
• sorts: the display function is a sorting algorithm in itself

1

//Header files for my tree library
#ifndef _TREE_H_
#define _TREE_H_
#include <stdlib.h>
#include <stdio.h>
//node structure that contains an char value and two node pointers
struct node
{
   char value;
   struct node *left;
   struct node *right;
};
typedef struct node Node;
 
//tree structure that contain the root node of the tree and a tmp node pointer
struct tree
{
   struct node *root;
   struct node *tmp;
};
typedef struct tree Tree;
 
//function prototypes
Tree *insert(Tree *, char);
void display(aTree);
 
#endif

1

//function display() prints out the contents of a binary
//search tree that stores characters in lexicographical order.
#include "tree.h"
//this functions uses recursion to display the contents of the tree
void display(Node *root)
{
   if( root != NULL)
   {
      display(root -> left);
      printf(" %c ,", root -> value);
      display(root -> right);
   }
}

1

//function insert() inserts a node to a given binary tree, if no tree
//exists it will create one and make the root node equal to the value given
#include "tree.h"
 
Tree *insert(Tree *aTree, char input)
{
   Node *tmpNode;
   tmpNode = malloc(sizeof(Node *));
   tmpNode -> value = input;
   if(aTree -> root != NULL)//if there is a tree
   {
      aTree -> tmp = aTree -> root;//setting a tmp pointer equal to the root
      while(aTree -> tmp -> value != tmpNode -> value)
      {
         if(tmpNode -> value < aTree -> tmp -> value)
         {
            if(aTree -> tmp -> left != NULL)
            {
               aTree -> tmp = aTree -> tmp -> left;
            }
            else
            {
               aTree -> tmp -> left = tmpNode;
            }
         }
         else
         {
            if(aTree -> tmp -> right != NULL)
            {
               aTree -> tmp = aTree -> tmp -> right;
            }
            else
            {
               aTree -> tmp -> right = tmpNode;
            }
         }
      }
   }
   else
   {
      aTree -> root = tmpNode;
   }
   return aTree;//return the tree with the new node added
   }

1

/*******************************************************
* Author: Dave Schoeffler                              *
* This program will utilize my own binary tree library *
* It will allow the user to create their own tree by   *
* choosing from a menu what operation they would like  *
* to perform.                                          *
*                                                      *
* Compile with: gcc -o tree tree.c -ltree -L.          *
*                                                      *
* Execute with: ./tree                                 *
*                                                      *
*******************************************************/
 
#include "tree.h"
 
int main()
{
   //aTree will be used to store the character values
   Tree *aTree;
   aTree = malloc(sizeof(Tree *));
   char input, choice, junk;
 
   //this menu allows the user to choose what operation they would like to perfor
   printf("Enter - 1 - to add a Node to the tree\n");
   printf("Enter - 2 - to display the contents of the tree in ascending order\n")
   printf("Enter - q - to quit\n");
   scanf("%c",&choice);
   scanf("%c",&junk);
   while( choice != 'q')
   {
      switch(choice)
      {
         //if they enter 1 they will be asked what character they would like to a
         case '1':
            printf("Please enter the character you would like to add to the tree:
            scanf("%c",&input);
            scanf("%c",&junk);
            aTree = insert(aTree, input);
            break;
         case '2'://if they choose 2 the tree will be displayed in lexicographica
            printf("The following values are contained in this binary tree: ");
            display(aTree -> root);
            printf("\n");
            break;
         case 'q':
         case 'Q':
            break;
         default:
            printf("Invalid input!\n");
            break;
      }
      printf("Enter - 1 - to add a Node to the tree\n");
      printf("Enter - 2 - to display the contents of the tree in ascending order\
      printf("Enter - q - to quit\n");
      scanf("%c",&choice);
      scanf("%c",&junk);
   }
   printf("The following values are contained in this binary tree: ");
   display(aTree -> root);// once they choose to quit the tree will be displayed
   printf("\n");
 
   return (0);
}

lab46:~/src/data/tree$ ./tree
Enter - 1 - to add a Node to the tree
Enter - 2 - to display the contents of the tree in ascending order
Enter - q - to quit
1
Please enter the character you would like to add to the tree: c
Enter - 1 - to add a Node to the tree
Enter - 2 - to display the contents of the tree in ascending order
Enter - q - to quit
1
Please enter the character you would like to add to the tree: b
Enter - 1 - to add a Node to the tree
Enter - 2 - to display the contents of the tree in ascending order
Enter - q - to quit
1
Please enter the character you would like to add to the tree: a
Enter - 1 - to add a Node to the tree
Enter - 2 - to display the contents of the tree in ascending order
Enter - q - to quit
2
The following values are contained in this binary tree:  a , b , c ,
Enter - 1 - to add a Node to the tree
Enter - 2 - to display the contents of the tree in ascending order
Enter - q - to quit
1
Please enter the character you would like to add to the tree: x
Enter - 1 - to add a Node to the tree
Enter - 2 - to display the contents of the tree in ascending order
Enter - q - to quit
q
The following values are contained in this binary tree:  a , b , c , x ,
lab46:~/src/data/tree$

This project was fairly last minute but I think I was able to get a good understanding of binary trees. I think having a good understanding of linked lists helped me create this tree library in a short amount of time. I didn't have time however to create a delete node function for the tree. Other than that I think I did fairly well on this project.

• http://en.wikipedia.org/wiki/Binary_search_tree
• C++ Programming D.S. Malik
• Matthew Haas
• Brandon Kennedy