Lab46 Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
======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:

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

=====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:

  * **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

=====Attributes=====

  * 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

=====Code=====

====Header File====
<code c 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

</code>

====Functions====
===display.c===
<code 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);
   }
}

</code>

===insert.c===
<code 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
   }

</code>

====Main Function====
===tree.c===
<code 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);
}

</code>

=====Execution=====

<cli>
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$

</cli>

=====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=====

    * [[http://en.wikipedia.org/wiki/Binary_search_tree]]
    * C++ Programming D.S. Malik
    * Matthew Haas
    * Brandon Kennedy
Lab46 Wiki

User Tools

Site Tools

Page Tools
