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

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

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

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

=====Background=====
The point of this project is to use a binary search tree to sort a list elements.
=====Scope=====
This program will utilize my functions in my tree library. These functions are insert() and display().

=====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 *
* 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);
}
</code>

=====Execution=====

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

</cli>

=====Reflection=====

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