Sidebar
Table of Contents
Project: Tree library implementation
A project for Data Structures by Brandon Kennedy during the Fall 2011 Semester.
This project was begun on November 1st and is anticipated to take 2 weeks. (give or take a few days for some fun)
Objectives
The purpose of this project is to better understand the functionality and use of a binary tree.
Prerequisites
In order to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved:
- The C programming guide
- A basic understanding of the tree structure
- understanding of node uses
Background
Through this project i am hoping to gain a better understanding of how to utilize a binary tree. I have planned to do this by implementing a tree of character values that will have the following functions:
- add a node
- remove a node
- print the current node values in order
I hope that after i finish this project i can use this tree type structure to help evaluate hand values in a poker implementation.
Scope
This implementation focuses specificaly on a tree of integer values. It will create a root node and from there it will classify each nodes placement based on the rule “if less go left, if more go right” simple as that!
Attributes
- Tree: This project will implement and utilize a binary tree
- Malloc: This code implements and utilized many forms of malloc
- Pointers: This code uses pointers to structs
- Linked lists: This code implements a singly linked list.
Code
Main.c
#include"tree.h" int main() { int input; Tree *mytree; mytree = malloc(sizeof(Tree *)); while(input != -1) { printf("Enter a positive integer value: "); scanf("%d", &input); if (input != -1) 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", &input); if(input == 1) { printf("Enter a positive integer value: "); scanf("%d", &input); mytree = add(mytree, input); } else if(input == 2) { printf("These are the values in the tree,\n"); printf("please enter a value to delete: "); postpr(mytree -> root); scanf("%d", &input); del(mytree, input); } postpr(mytree -> root); printf("\n"); return 0; }
Add.c
/* * 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, int 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; printf("smaller\n"); } else mytree -> tmp -> smaller = grep; } else { if(mytree -> tmp -> bigger != NULL) { mytree -> tmp = mytree -> tmp -> bigger; printf("bigger\n"); } else mytree -> tmp -> bigger = grep; } } } else { mytree -> root = grep; } return mytree; }
del.c
#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; }
print.c
#include"tree.h" void postpr(Node *lantro) { if(lantro != NULL) { postpr(lantro -> smaller); printf("%d, ", lantro -> value); postpr(lantro -> bigger); } }
tree.h
#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; #endif
Execution
lab46:~/src/DataS/Project4$ ./main Enter a positive integer value: 4 Enter a positive integer value: 7 bigger Enter a positive integer value: 2 smaller Enter a positive integer value: 8 bigger bigger Enter a positive integer value: 3 smaller bigger Enter a positive integer value: 6 bigger smaller Enter a positive integer value: 1 smaller smaller Enter a positive integer value: 5 bigger smaller smaller Enter a positive integer value: -1 Enter - 1 - to add a node Enter - 2 - to delete a node Enter - 3 - to print the nodes in post order 3 1, 2, 3, 4, 5, 6, 7, 8, lab46:~/src/DataS/Project4$
Reflection
Be careful what you type! As we were editing this program in VIM we entered the wrong file name to open with :vsp. After that, matt had me do a :r filename. What this did was make a copy of the file we were editing in the wrong file we had opened before. That sucked… Other than that, trees are a wonderful, magical thing! As the tree traverses, say in a searching function, each branch it moves down it removes all other branches on the tree from being possible entries to find.
