//Hailey Hanson
2 //CS 222 Programming Assignment #3
3 //January 21, 2014
4
5 //This program should prompt the user with a '>' to enter a series of commands which can be found under the help menu
6 //If the user enters an integer, that integer will be added to their tree. They can then search their tree, delete things from the tree and print the tree out
7
8 #include
9 #include
10 #include
11 #include
12
13 //Node Structure
14 /*********************************************************/
15 struct node{ //
16 int data; //
17 struct node *right, *left; //
18 }; //
19 /********************************************************/
20
21 //Insert Function
22 /******************************************************/
23 //This function should insert integers into the tree, arranging them
24 //in infix order so that the middle value is at the root of the tree
25 struct node* insert(struct node *root, int num){
26 if (root == NULL){
27 root=malloc(sizeof(struct node));
28 root->data=num;
29 root->left=root->right=NULL;
30 return(root);
31 }//end of if
32 else if (num < root->data){
33 root->left = insert(root->left, num);
34 return(root);
35 }//end of else if
36 else if (num > root->data){
37 root->right = insert(root->right, num);
38 return(root);
39 }//end of else if
40 }//end of insert function
41 /******************************************************/
42
43
44 //Traverse List Function
45 /********************************************************/
46 int traverse(struct node *root){
47 if (root == NULL) {return(0);}
48 else{
49 int count_left, count_right;
50 count_left=traverse(root->left);
51 printf("%d ", root->data);
52 count_right=traverse(root->right);
53 if (count_left>count_right) return(count_left+1);
54 else return (count_right+1);
55 }//end of else
56 }//end of traverse function
57 /********************************************************/
58
59 //Depth Function
60 /*******************************************************/
61 //to be called within the balance function
62 int depth(struct node *root){
63 if (root == NULL) return (0);
64 else {
65 int count_left, count_right;
66 count_left=depth(root->left);
67 count_right=depth(root->right);
68 if (count_left>count_right) return(count_left+1);//return larger depth value
69 else return (count_right+1); //of return smaller
70 }//end of else
71 }//end of depth ftn
72 //should return deepest tree length
73 /*******************************************************/
74
75
76 //Balanced/Not Balanced Function
77 /*******************************************************/
78 int balance(struct node *root){
79 if (root == NULL) return 1;
80 if ((balance(root->left)) &&(balance(root->right)) && (abs(depth(root->left)-depth(root->right))<=1))
81 return 1;
82 return 0;
83 }//end of balance function
84 /******************************************************/
85
86 //Search Function
87 /*******************************************************/
88 //searches tree for an integer
89 int search(struct node *root, int num){ //ftn takes in the tree and a number to search for the number in the tree
90 if (root == NULL) return (0);
91 if (num == root->data) return (1);
92 if (num > root->data){
93 return search (root->right, num);
94 }//end of if
95 if (num < root->data){
96 return (search (root->left, num));
97 }//end of if
98 }//end of search function
99 /*********************************************************/
100
101 //Delete Function
102 /********************************************************/
103 //deletes a node from the tree
104 struct node* delete(struct node *root, int num){
105 if (root == NULL) return(NULL);
106
107 if (num
108 root->left=delete(root->left, num);
109 }//end of else if
110
111 else if (num>root->data){
112 root->right=delete(root->right, num);
113 }//end of else if
114
115 else {
116 if ((root->left == NULL) && (root->right == NULL)){ //if root has no children
117 free(root); //free root
118 return(NULL);
119 }//end of if
120 if ((root->left != NULL) && (root->right == NULL)){ //if root has only left child
121 struct node *temp = root->left;
122 free(root); //free left child
123 return(temp);
124 }//end of if
125 if ((root->left == NULL) && (root->right != NULL)){ //if root has only right child
126 struct node *temp = root->right;
127 free(root); //free right child
128 return(temp);
129 }//end of if
130 if ((root->left != NULL) && (root->right != NULL)){ //if root has two children
131 struct node *temp = root->right; //temp is the successor of root
132 while (temp->left != NULL)
133 temp=temp->left; //traverse to the left
134 root->data=temp->data;
135 root->right=delete(root->right, temp->data); //recursively delete node with temp's data
136 return(root);
137 }//end of if
138 else printf("To proceed to the help menu, type a ? \n");
139 return(root);
140 }//end of else
141 return(root);
142 }//end of delete ftn
143
144 /*********************************************************/
145
146
147 //HELP MENU
148 /*********************************************************/
149 //helps a brutha out
150 void help(){
151
152 printf("******************************************HELP MENU*************************************************\n");
153 printf("If you wish to EXIT the program, type 'Q' at any time (with no quotes)\n");
154 printf("If you wish to ADD a number to the tree, just type an integer and then hit enter\n");
155 printf("If you wish to SEARCH for a number in the tree, type an s followed by a space and then the integer.\n");
156 printf("If you wish to DELETE a number from the tree, type a d followed by a space and then the integer.\n");
157 printf("If you wish to see the entire tree, type a p and then hit enter\n");
158 printf("To return to this help menu, type a ?\n");
159 printf("****************************************************************************************************\n");
160 }//end of help menu
161
162 /*********************************************************/
163
164 int main(){
165
166 //Binary Tree Formation
167 /**********************************************************/
168 struct node *root;
169 root=NULL;
170 int num;
171 /**********************************************************/
172
173 //Receiving Input from User
174 /*********************************************************/
175
176 while (1){ //This will keep my loop going so the user puts multiple inputs in the tree
177
178 char input[6];
179
180 printf(">"); //prompt
181 fgets(input, 256, stdin);
182
183 char mode; //choice of Q, s, d, p or ?
184 int num; //number in tree
185
186 int type_1, type_2, type_3;
187
188 type_2 = sscanf(input, "%c %d", &mode, &num); //user entered a mode, then a number
189 type_1 = sscanf(input, "%d", &num); //user entered just a number
190 type_3 = sscanf(input, "%c", &mode); //should be a ? or p
191
192 if((type_3 == 1) && (type_2 != 2) && (type_1 != 1)){ //If user enters a character, not two characters or 1 number
193 switch (mode)
194 {
195 case 'p':
196 printf("\nMax Depth = %d\n", traverse(root)); //If user enters p, print max dep th from traverse function
197 if (balance(root) == 1) printf("\nTree is Balanced\n");
198 else printf("\nTree is NOT Balanced\n");
199 break;
200 case '?': help(); //if user enters ?, send to help menu
201 break;
202 case 'Q': exit(0); //if user enters Q, quit program
203 break;
204 default: printf("\nYou have entered an incorrect input. Proceed to the help menu. Do not pass go. Do not collect $200.\n\n");
205 help(); //if user is incompetent, send to help menu
206 break;
207 }//end of switch
208 }//end of if statement
209 else if ((type_2 == 2) && (type_1 != 1)) { //if user enters a char and a num
210 switch (mode)
211 {
212 case 's': search(root, num); //if user enters s followed by number, search tree for th at number
213 if (search(root, num) == 1) printf("%d Is already in the tree\n", num);
214 else printf("%d is not in the tree\n", num);
215 break;
216 case 'd':
217 if(search(root, num) ==1) root=delete(root, num);
218 else printf("%d is not in the list\n", num);
219 break;
220 default: printf("\nYou have entered an incorrect input. Proceed to the help menu. Do not pass go. Do not collect $200.\n\n");
221 help(); //if user is incompetent, send to help menu
222 break;
223 }//end of switch
224 }//end of else if
225 else if (type_1 == 1){ //if user enters 1 number
226 if((search(root , num)) == 1)printf("%d Is already in the tree\n", num);
227
228 else{
229 root=insert(root, num);
230 printf("%d has been added to the tree\n", num);
231 }//end of else
232 }//end of else if
233
234 else{ //else if user is completely disoriented and overwhelmed, send to help menu.
235 printf("\nYou have entered an incorrect input. Proceed to the help menu. Do not pass go. Do not c ollect $200.\n\n");
236 help();
237 }//end of else
238
239 }//end of while(1)
240 }//end of main
No comments:
Post a Comment