# Thread: Binary Tree, couple questions

1. ## Binary Tree, couple questions

Code:
```/*
File: btree.c
Date: 3/10/05
Info: Binary tree implementation.

Sean
*/

#include <stdio.h>
#include <stdlib.h>

/* verbose output */
#define DEBUG

/* structures */
struct node {
int data;
struct node *left;
struct node *right;
};

struct btree {
struct node *root;
struct node *cur;
struct node *prev;
};

/* prototypes */
int btree_initialize(int data, struct btree *tree);
int btree_insert(int data, struct btree *tree);
struct node * btree_find(int data, struct btree *tree);
struct node * btree_find_node(int data, struct node *cur);
void btree_delete(struct btree *tree);
void btree_delete_all(struct node *cur);
void btree_print(struct btree *tree);
void btree_print_all(struct node *cur);

int main(void)
{
struct btree tree;

btree_initialize(10, &tree); /* initialize root node to 10 */

/* insert nodes */
btree_insert(5,&tree);
btree_insert(6,&tree);
btree_insert(14,&tree);
btree_insert(14,&tree);

/*
Current tree should look something like this:

10
/      \
5       14
/ \     /  \
N   6    N   N

*/

/* check the tree for certain values */

btree_print(&tree); /* print the tree */

btree_delete(&tree); /* delete the tree */

getchar();

return 0;
}

/*
First function that should be called on the binary tree. Basically
defines the root node and sets its value to 'data'. The function
returns -1 if initialization fails and 0 if it is successful.
*/
int btree_initialize(int data, struct btree *tree)
{
struct node *tmp = NULL;

tmp = malloc(sizeof(struct node));
if (!tmp) {
#ifdef DEBUG
puts("btree_initialize: unable to allocate memory");
#endif

return -1;
}

tmp->data = data;
tmp->left = NULL;
tmp->right = NULL;

tree->root = tmp;
tree->cur = tree->root;

#ifdef DEBUG
puts("btree_initialize: root node initialized");
#endif

return 0;
}

/*
This function searches the entire binary for the value 'data'.
A pointer to the node containing 'data' is returned if it is
found. Otherwise, NULL is returned.
*/
struct node * btree_find(int data, struct btree *tree)
{
struct node *ret = NULL;

/* just make sure tree->cur points to root for search */
tree->cur = tree->root;

#ifdef DEBUG
printf("btree_find: trying to find %d\n",data);
#endif

/* function that does the actual search */
ret = btree_find_node(data, tree->cur);

#ifdef DEBUG
if (ret) {
printf("btree_find: found %d\n",data);
} else {
printf("btree_find: did not find %d\n",data);
}
#endif

return ret;
}

/*
This function searches the tree recursively for 'data'. It
traverses to the left until it reaches a leaf, then it traverses
right. All functions will return once 'data' is found. Otherwise,
execution continues until the tree has been fully searched.
*/
struct node * btree_find_node(int data, struct node *cur)
{
struct node *ret = NULL;

if (cur) { /* node is not NULL */
if (cur->data == data) {
return cur;
}
else { /* continue searching */
#ifdef DEBUG
puts("btree_find_node: searching left");
#endif
ret = btree_find_node(data,cur->left);
if (ret != NULL) { /* node has been found */
return ret;
}

#ifdef DEBUG
puts("btree_find_node: searching right");
#endif
ret = btree_find_node(data,cur->right);
if (ret != NULL) { /* node has been found */
return ret;
}

return NULL;
}
}
else {
return NULL;
}
}

/*
Inserts a node containing 'data'. If 'data' already exists in the tree,
no new node will be added and 1 will be returned. Otherwise, 'data' will
be added to the left or right depending on how it compares to the value
of the current node. On successful insertion, 0 is returned.
*/
int btree_insert(int data, struct btree *tree)
{
if (tree->cur) { /* node is not NULL */
if (data < tree->cur->data) { /* insert to the left */
tree->prev = tree->cur;
tree->cur = tree->cur->left;
#ifdef DEBUG
puts("btree_insert: traversing left");
#endif
return btree_insert(data, tree);
}
else if (data > tree->cur->data) { /* insert to the right */
tree->prev = tree->cur;
tree->cur = tree->cur->right;
#ifdef DEBUG
puts("btree_insert: traversing right");
#endif
return btree_insert(data, tree);
}
else { /* data already in tree, don't insert */
#ifdef DEBUG
#endif
tree->cur = tree->root;
return 1;
}
}
else { /* node is NULL, so we add */
struct node *tmp = NULL;

tmp = malloc(sizeof(struct node));
if (!tmp) {
#ifdef DEBUG
puts("btree_insert: unable to allocate memory");
#endif
return -1;
}

tmp->data = data;
tmp->left = NULL;
tmp->right = NULL;

tree->cur = tmp;

/* add new node to correct side of parent node */
if (data < tree->prev->data) {
tree->prev->left = tree->cur;
}
else {
tree->prev->right = tree->cur;
}

tree->cur = tree->root; /* reset tree->cur for next insert */

#ifdef DEBUG
printf("btree_insert: node added with value %d",data);
#endif

return 0;
}
}

/*
Prints out the entire binary tree, one node per line. First, all of the nodes
to the left are covered, then all of the nodes to the right of the current
node.
*/
void btree_print(struct btree *tree)
{
btree_print_all(tree->root);
}

/*
Prints the entire list.
*/
void btree_print_all(struct node *cur)
{
if (cur) { /* node is not NULL */
btree_print_all(cur->left);
btree_print_all(cur->right);

printf("%d ",cur->data);
}
}

/*
Deletes the entire binary tree, freeing all allocated memory.
*/
void btree_delete(struct btree *tree)
{
/* delete the entire tree */
btree_delete_all(tree->root);

tree->root = NULL;
tree->cur = NULL;
tree->prev = NULL;
}

/*
This function deletes the entire binary tree by traversing each path and
deleting each leaf.
*/
void btree_delete_all(struct node *cur)
{
if (cur) { /* current node isn't NULL */
btree_delete_all(cur->left);
btree_delete_all(cur->right);

/* once both of these have returned, we know */
/* that we have reached a leaf.              */
free(cur);
}
}```
At the bottom of my code, I delete the entire tree. I was wondering if I'm doing this currently. Should I be passing a double pointer to btree_delete_all()? I tried searching the tree immediately after deleting the list, and the tree appeared to have been deleted. I just wanna double check Also, is there a better way of printing out the tree? As it is, the function will just go down to to the furthest node and prints from the bottom up (kinda).

Any other suggestions/tips?

Thanks  2. This is a good place to use recursive functions. To print the contents in order, you might want to do something like:
Code:
```void printbst(struct node* rootPtr)
{
if(rootPtr != NULL)
{
printbst(rootPtr->leftPtr);
printf(" %d\n", rootPtr->data);
printbst(rootPtr->rightPtr);
}
}```
the free function is really similar, but instead of a print statement in the middle, use a free() call at the bottom.
Code:
```void freenodes(struct node* rootPtr)
{
if(rootPtr != NULL)
{
freenodes(rootPtr->leftPtr);
freenodes(rootPtr->rightPtr);
free(rootPtr);
}
}```
Should do the trick. 3. Originally Posted by dinjas
This is a good place to use recursive functions. To print the contents in order, you might want to do something like:
Code:
```void printbst(struct node* rootPtr)
{
if(rootPtr != NULL)
{
printbst(rootPtr->leftPtr);
printf(" %d\n", rootPtr->data);
printbst(rootPtr->rightPtr);
}
}```
I didn't think about printing it out that way, thanks And I think my delete code is pretty much the same as yours  4. Originally Posted by scoobasean
I didn't think about printing it out that way, thanks And I think my delete code is pretty much the same as yours Three common ways to print out binary trees are as follows:

Preorder Traversal:
Code:
```void PrintPreorder(struct node* root)
{
if(root)
{
printf(" %d\n", root->data);
PrintPreorder(root->left);
PrintPreorder(root->right);
}
}```
In-order Traversal
Code:
```void PrintInorder(struct node* root)
{
if(root)
{
PrintInorder(root->left);
printf(" %d\n", root->data);
PrintInorder(root->right);
}
}```
Postorder Traversal
Code:
```void PrintPostorder(struct node* root)
{
if(root)
{
PrintPostorder(root->left);
PrintPostorder(root->right);
printf(" %d\n", root->data);
}
}``` Popular pages Recent additions 