A
arnuld
A Binary Search Tree implemented in C. Any advice on how to complete the
one remained function ?
/* A Binary tree learned from "The Practice of Programming", section
2.8 . Its a little bit different though. It also includes the
* count of each element added into the tree. Currentlly it supports 3
functions: adding an element, printing and free()ing the whole
* tree. Only one fucntion, the deletion of a single element, have
remained.
*
*
* VERSION 0.0
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
enum { SIZE_NAME = 30 };
/* One disadvantage of using char [] as a struct memeber is the size of
name is limited. but if we use char* there will be no limit
on the size then. */
struct namev
{
char name[SIZE_NAME];
int cnt;
struct namev* left;
struct namev* right;
};
struct namev* tree_add_name(struct namev*, char* );
void tree_free(struct namev* );
void tree_print(struct namev* );
struct namev* tree_delete_name(struct namev*, char*);
int main(void)
{
struct namev* root = NULL;
root = tree_add_name(root, "comp.lang.c");
root = tree_add_name(root, "comp.lang.c++");
root = tree_add_name(root, "comp.lang.lisp");
root = tree_add_name(root, "comp.unix.programmer");
root = tree_add_name(root, "comp.unix.programmer");
root = tree_add_name(root, "comp.lang.c");
root = tree_add_name(root, "comp.lang.");
tree_print(root);
return 0;
}
struct namev* tree_add_name(struct namev* r, char* name)
{
int cmp;
if(NULL == name)
{
fprintf(stderr, "FILE: %s, LINE: %d : No name provided\n",
__FILE__, __LINE__);
return r;
}
if(NULL == r) /* We got a new element */
{
r = malloc(1 * sizeof *r);
if(NULL == r)
{
fprintf(stderr,"FILE: %s, LINE: %d : malloc() failed\n",
__FILE__, __LINE__);
return NULL;
}
strcpy(r->name, name);
r->cnt = 1;
r->left = r->right = NULL;
}
else if(0 == (cmp = strcmp(name, r->name)))
{
r->cnt++;
}
else if(cmp < 0)
{
r->left = tree_add_name(r->left, name);
}
else
{
r->right = tree_add_name(r->right, name);
}
return r;
}
void tree_free(struct namev* r)
{
if(r)
{
tree_free(r->left);
tree_free(r->right);
tree_free(r);
r = NULL;
}
}
void tree_print(struct namev* r)
{
if(r)
{
tree_print(r->left);
printf("name = %s, count = %d\n", r->name, r->cnt);
/* how can I keep those printed elements properly aligned ? */
tree_print(r->right);
}
}
struct namev* tree_delete_name(struct namev* e, char* c)
{
int cmp;
if(NULL == e || NULL == c)
{
fprintf(stderr, "FILE: %s, LINE: %d: NUL arguments\n", __FILE__,
__LINE__);
return e;
}
else if(0 == (cmp = strcmp(c, e->name)))
{
/* How can keep the pointers/left-right intact after free()ing
this ?
or I am just dealing with a theoretical problem. Practically, we
never remove a single element from a tree ?? */
}
else if(cmp < 0)
{
tree_delete_name(e->left, c);
}
else
{
tree_delete_name(e->right, c);
}
return e;
}
=================== OUTPUT ==========================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra binary-tree.c
[arnuld@dune programs]$ ./a.out
name = comp.lang., count = 1
name = comp.lang.c, count = 2
name = comp.lang.c++, count = 1
name = comp.lang.lisp, count = 1
name = comp.unix.programmer, count = 2
[arnuld@dune programs]$
one remained function ?
/* A Binary tree learned from "The Practice of Programming", section
2.8 . Its a little bit different though. It also includes the
* count of each element added into the tree. Currentlly it supports 3
functions: adding an element, printing and free()ing the whole
* tree. Only one fucntion, the deletion of a single element, have
remained.
*
*
* VERSION 0.0
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
enum { SIZE_NAME = 30 };
/* One disadvantage of using char [] as a struct memeber is the size of
name is limited. but if we use char* there will be no limit
on the size then. */
struct namev
{
char name[SIZE_NAME];
int cnt;
struct namev* left;
struct namev* right;
};
struct namev* tree_add_name(struct namev*, char* );
void tree_free(struct namev* );
void tree_print(struct namev* );
struct namev* tree_delete_name(struct namev*, char*);
int main(void)
{
struct namev* root = NULL;
root = tree_add_name(root, "comp.lang.c");
root = tree_add_name(root, "comp.lang.c++");
root = tree_add_name(root, "comp.lang.lisp");
root = tree_add_name(root, "comp.unix.programmer");
root = tree_add_name(root, "comp.unix.programmer");
root = tree_add_name(root, "comp.lang.c");
root = tree_add_name(root, "comp.lang.");
tree_print(root);
return 0;
}
struct namev* tree_add_name(struct namev* r, char* name)
{
int cmp;
if(NULL == name)
{
fprintf(stderr, "FILE: %s, LINE: %d : No name provided\n",
__FILE__, __LINE__);
return r;
}
if(NULL == r) /* We got a new element */
{
r = malloc(1 * sizeof *r);
if(NULL == r)
{
fprintf(stderr,"FILE: %s, LINE: %d : malloc() failed\n",
__FILE__, __LINE__);
return NULL;
}
strcpy(r->name, name);
r->cnt = 1;
r->left = r->right = NULL;
}
else if(0 == (cmp = strcmp(name, r->name)))
{
r->cnt++;
}
else if(cmp < 0)
{
r->left = tree_add_name(r->left, name);
}
else
{
r->right = tree_add_name(r->right, name);
}
return r;
}
void tree_free(struct namev* r)
{
if(r)
{
tree_free(r->left);
tree_free(r->right);
tree_free(r);
r = NULL;
}
}
void tree_print(struct namev* r)
{
if(r)
{
tree_print(r->left);
printf("name = %s, count = %d\n", r->name, r->cnt);
/* how can I keep those printed elements properly aligned ? */
tree_print(r->right);
}
}
struct namev* tree_delete_name(struct namev* e, char* c)
{
int cmp;
if(NULL == e || NULL == c)
{
fprintf(stderr, "FILE: %s, LINE: %d: NUL arguments\n", __FILE__,
__LINE__);
return e;
}
else if(0 == (cmp = strcmp(c, e->name)))
{
/* How can keep the pointers/left-right intact after free()ing
this ?
or I am just dealing with a theoretical problem. Practically, we
never remove a single element from a tree ?? */
}
else if(cmp < 0)
{
tree_delete_name(e->left, c);
}
else
{
tree_delete_name(e->right, c);
}
return e;
}
=================== OUTPUT ==========================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra binary-tree.c
[arnuld@dune programs]$ ./a.out
name = comp.lang., count = 1
name = comp.lang.c, count = 2
name = comp.lang.c++, count = 1
name = comp.lang.lisp, count = 1
name = comp.unix.programmer, count = 2
[arnuld@dune programs]$