Table of Contents

Project: Binary Tree Library Implementation

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.

Objectives

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.

Prerequisites

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

Background

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

Scope

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:

Attributes

Code

Header File

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

Functions

display.c

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);
   }
}

insert.c

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
   }

Main Function

tree.c

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);
}

Execution

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$

Reflection

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.

References