A project for data Structures by Brandon Kennedy during the Fall 2011 Semester.

This project was begun on 12-5-2011 and is anticipated to take 1 day.

State the purpose of this project. What is the point of this project? What do we hope to accomplish by undertaking it?

The purpose of this project is to create a character sorting program that will sort characters by their ascii values. By undertaking this project I hope to walk away with a better understanding of trees.

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

• the C programming guide
• knowledge of the alphebet
• ability to re-use a library
• practice with tree-based liked lists.

The purpose of this project is to develop a better understanding of the tree data structure and to implement a character sorting program. For the data structures EoCE we had to create a character sorting tree, so here it is in project from. The tree will sort received characters beased on their ascii value.

Give a general overview of your anticipated implementation of the project. Address any areas where you are making upfront assumptions or curtailing potential detail. State the focus you will be taking in implementation.

I will be focusing on a tree structure that will save character values. I will traverse the tree for printing via recursion, and i will re-use a linrary to do it all.

State and justify the attributes you'd like to receive upon successful approval and completion of this project.

• attribute1: pointers → this program uses pointers to nodes.
• attribute2: trees → this program instanciates a tree based data structure.
• attribute3: sorts → When this program outputs it will sort the data by recursion
• attribute4: libraries → this program will use a library.

#include"tree.h"

int main()
{
        char input; //user character input
        int choice; // operation choice of user
        Tree *mytree; //tree instance
        mytree = malloc(sizeof(Tree *));
        while(input != '#')
        { //accept input and load the tree with values
                printf("Enter a character(# to exit): ");
                scanf("%c", &input);
                getchar(); //scanning for junk values
                if (input != '#')
                        mytree = add(mytree, input);
        }
        printf("Enter - 1 - to add a node\n");
        printf("Enter - 2 - to delete a node\n");
        printf("Enter - 3 - to print the nodes in post order\n");
        scanf("%d", &choice);
        if(choice == 1)
        { //adding a node
                printf("Enter a character(# to exit): ");
                scanf("%c", &input);
                getchar();
                mytree = add(mytree, input);
        }
        else if(choice == 2)
        {//delete a node
                printf("These are the values in the tree,\n");
                printf("please enter a value to delete: ");
                postpr(mytree -> root);
                scanf("%c", &input);
                del(mytree, input);
        }
        //choice 3 isnt needed because i am printing after each choice anyways, so if they enter a 3, nothing operates except the print.
        postpr(mytree -> root);
        printf("\n");
        return 0;
}

/*
* add.c, a tree manipulation function.
* Made by Brandon Kennedy for Data Structures
* Semester: Fall: 2011
*
* prototype: Tree *add(Tree *, char);
* Returns a tree struct containing the address of the root, tmp, tmp2, and solo nodes..
*/
#include"tree.h"
 
Tree *add(Tree *mytree, char val)
{
        Node *grep;
        grep = malloc(sizeof(Node *));
        grep -> value = val;
        if(mytree -> root != NULL)
        {
                mytree -> tmp = mytree -> root;
                while(mytree -> tmp -> value != val)
                {
                        if(val < mytree -> tmp -> value)
                        {
                                if(mytree -> tmp -> smaller != NULL)
                                {
                                        mytree -> tmp = mytree -> tmp -> smaller;
                                }
                                else
                                        mytree -> tmp -> smaller = grep;
                        }
                        else
                        {
                                if(mytree -> tmp -> bigger != NULL)
                                {
                                        mytree -> tmp = mytree -> tmp -> bigger;
                                }
                                else
                                        mytree -> tmp -> bigger = grep;
                        }
                }
        }
        else
        {
                mytree -> root = grep;
        }
        return mytree;
}

#include"tree.h"
 
Tree *del(Tree *mytree, char val)
{
        if(mytree -> root != NULL)
        {
                mytree -> tmp = mytree -> root;
                while(mytree -> tmp -> value != val)
                {
                        if(val < mytree -> tmp -> value)
                        {
                                if(mytree -> tmp -> smaller -> value = val)
                                {
                                        mytree -> solo = mytree -> tmp -> smaller;
                                        mytree -> tmp2 = mytree -> solo -> bigger;
                                        while(mytree -> tmp2 -> smaller != NULL)
                                        {
                                                mytree -> tmp2 = mytree -> tmp2 -> smaller;
                                        }
                                        mytree -> tmp2 -> smaller = mytree -> solo -> smaller;
                                        mytree -> tmp -> smaller = mytree -> solo -> bigger;
                                        mytree -> solo -> smaller = NULL;
                                        mytree -> solo -> bigger = NULL;
                                        free(mytree -> solo);
                                }
                                else
                                        mytree -> tmp = mytree -> tmp -> smaller;
                        }
                        else
                        {
                                if(mytree -> tmp -> bigger -> value = val)
                                {
                                        mytree -> solo = mytree -> tmp -> bigger;
                                        mytree -> tmp2 = mytree -> solo -> bigger;
                                        while(mytree -> tmp2 -> smaller != NULL)
                                        {
                                                mytree -> tmp2 = mytree -> tmp2 -> smaller;
                                        }
                                        mytree -> tmp2 -> smaller = mytree -> solo -> smaller;
                                        mytree -> tmp -> smaller = mytree -> solo -> bigger;
                                        mytree -> solo -> smaller = NULL;
                                        mytree -> solo -> bigger = NULL;
                                        free(mytree -> solo);
                                }
                                else
                                        mytree -> tmp = mytree -> tmp -> bigger;
                        }
                }
        }
        return mytree;
}

#include"tree.h"
 
void postpr(Node *lantro)
{
        if(lantro != NULL)
        {
                postpr(lantro -> smaller);
 
                printf("%c, ", lantro -> value);
                postpr(lantro -> bigger);
        }
}

#ifndef _TREE_H_
#define _TREE_H_
#include<stdlib.h>
#include<stdio.h>
 
struct node{
        char value;
        struct node *bigger;
        struct node *smaller;
};
typedef struct node Node;
 
struct tree{
        struct node *root;
        struct node *tmp;
        struct node *tmp2;
        struct node *solo;
};
typedef struct tree Tree;
 
Tree *add(Tree*, char);
Tree *del(Tree*, char);
void postpr(Node*);
#endif

lab46:~/src/DataS/Project4$ ./main
Enter a character(# to exit): d
Enter a character(# to exit): e
Enter a character(# to exit): y
Enter a character(# to exit): g
Enter a character(# to exit): a
Enter a character(# to exit): n
Enter a character(# to exit): o
Enter a character(# to exit): d
Enter a character(# to exit): s
Enter a character(# to exit): #
Enter - 1 - to add a node
Enter - 2 - to delete a node
Enter - 3 - to print the nodes in post order
3
a, d, e, g, n, o, s, y,
lab46:~/src/DataS/Project4$

Comments/thoughts generated through performing the project, observations made, analysis rendered, conclusions wrought. What did you learn from doing this project?

Trees are a very useful data structure that can be implemented in many different ways. They can be used to realistically sort almost any type of data and are very easy to understand.

Through this project I was able to catch a glimps of the awesomeness of recursion. I am using it to print out the tree without having to worry about backtracking, because when one iteration ends, the other is already there.