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.

This project will utilize my own binary tree library to sort a tree of elements

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 use a binary tree data structure

The point of this project is to use a binary search tree to sort a list elements.

This program will utilize my functions in my tree library. These functions are insert() and display().

• 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 *
* to accept as input unique characters from the user   *
* and store them in a binary tree. After that it will  *
* display the characters in lexiographical order.      *
*                                                      *
* Compile with: gcc -o tree tree.c -ltree -L.          *
*                                                      *
* Execute with: ./tree                                 *
*                                                      *
*******************************************************/
 
#include "tree.h"//my tree library
 
int main()
{
   //declaration of a Tree struc that will be used to store the characters
   Tree *aTree;
   aTree = malloc(sizeof(Tree *));
   char choice, junk;//variable choice will be used to store the current
                     //character from the user
   printf("Enter a letter( '.' to quit): ");//user prompt for input
   scanf("%c",&choice);
   scanf("%c",&junk);
   while( choice != '.')
   {
      aTree = insert(aTree, choice);//this line sends the character to the
                                    //insert node function
      printf("Enter a letter( '.' to quit): ");
      scanf("%c",&choice);
      scanf("%c",&junk);
   }
   printf("The following values are contained in this binary tree: ");
   display(aTree -> root);//displays the tree values in lexigraphical order
   printf("\n");
 
   return (0);
}

lab46:~/src/data/eoce/0x4$ ./tree
Enter a letter( '.' to quit): b
Enter a letter( '.' to quit): d
Enter a letter( '.' to quit): e
Enter a letter( '.' to quit): f
Enter a letter( '.' to quit): c
Enter a letter( '.' to quit): a
Enter a letter( '.' to quit): g
Enter a letter( '.' to quit): .
The following values are contained in this binary tree:  a , b , c , d , e , f , g ,
lab46:~/src/data/eoce/0x4$

This project was fairly because it was fairly similar to my other tree implementation. All I had to do was rewrite my main function and I was done.

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