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.
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.
In order to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved:
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
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:
//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
//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); } }
//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 }
/******************************************************* * 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); }
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$
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.