Code:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>
typedef struct Bin_Node
{
int data;
struct Bin_Node *left;
struct Bin_Node *right;
}Bin_Node;
typedef struct Bin_Tree
{
struct Bin_Node *root; //same as head node in a linked list
int node_count;
}Bin_Tree;
typedef struct Trunk
{
struct Trunk *previous;
char mystr[20];
}Trunk;
Bin_Tree *create_tree(void);
Bin_Tree *initalize_tree(Bin_Tree *tree);
Bin_Node *create_node(void);
Bin_Node *initalize_node(Bin_Node *node, int data);
bool insert_node(Bin_Node **root, Bin_Node *node);
void print_tree(const Bin_Node *root);
void destroy_tree(Bin_Node *root);
void insert(Bin_Tree *tree, int node_data);
void print(const Bin_Tree *tree);
void destroy(Bin_Tree *tree);
// functions created to use c++ code
Trunk *create_trunk(void);
Trunk *initalize_trunk(Trunk *p, char strpassed[]);
void insert_trunk(Bin_Tree *tree);
// copied from c++ code
void show_trunks(Trunk *p);
void print_tree_and_trunk(Bin_Node *root, Trunk *p, bool isleft);
int main()
{ //10,6,,3,9,2,3,13,54,20,43
int i, nums[] = {10, 6, 3, 9, 2, 3, 13, 54, 20, 43};
Bin_Tree *tree, *tree_trunk;
tree = create_tree();
for (i = 0; i < 10; i++)
{
insert(tree, nums[i]);
}
print(tree);
destroy(tree);
tree_trunk = create_tree();
insert_trunk(tree_trunk);
print(tree_trunk);
destroy(tree_trunk);
free(tree);
free(tree_trunk);
return 0;
}
Bin_Tree *create_tree(void)
{
Bin_Tree *tmp_tree = malloc(sizeof(Bin_Tree));
assert(tmp_tree != NULL);
tmp_tree = initalize_tree(tmp_tree);
return tmp_tree;
}
Bin_Tree *initalize_tree(Bin_Tree *tree)
{
tree->node_count = 0;
tree->root = NULL;
return tree;
}
Bin_Node *create_node(void)
{
return malloc(sizeof(Bin_Node));
}
Bin_Node *initalize_node(Bin_Node *node, int data)
{
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
bool insert_node(Bin_Node **root, Bin_Node *node)
{
if (!*root) //parent node has no children??
{
*root = node;
return true;
}
else
{
if ((*root)->data < node->data) //the data of the parent we are looking at is less than the data of the node so go to its right child
{
return insert_node(&(*root)->right, node);
}
else if ((*root)->data != node->data)
{
return insert_node(&(*root)->left, node);
}
}
return false; // the node already existed
}
void print_tree(const Bin_Node *root)
{
if (!root)
{
return;
}
if (root->left) //parent node has a child to the left
{
print_tree(root->left);
printf("searching left child of %d\n", root->data);
}
printf("node data = %d\n", root->data);
if (root->right) //parent node has a child to the right
{
print_tree(root->right);
printf("searching right child of %d\n", root->data);
}
}
void destroy_tree(Bin_Node *root)
{
if (root) //parent has children
{
destroy_tree(root->left);
destroy_tree(root->right);
free(root);
printf("node deleated\n");
}
}
void insert(Bin_Tree *tree, int node_data)
{
Bin_Node *root = tree->root, *node;
node = create_node();
assert(node != NULL);
node = initalize_node(node, node_data);
if (!insert_node(&root, node)) //node already exists
{
free(node);
fprintf(stderr, "value already exists\n");
}
else
{
if (!tree->root)
{
tree->root = node;
}
tree->node_count++;
}
}
void print(const Bin_Tree *tree)
{
Bin_Node *root = tree->root;
//print_tree(root);
print_tree_and_trunk(root, NULL, false);
printf("\nthere are %d nodes in the tree\n\n", tree->node_count);
}
void destroy(Bin_Tree *tree)
{
Bin_Node *root = tree->root;
destroy_tree(root);
}
// functions created to use c++ code
Trunk *create_trunk(void)
{
return malloc(sizeof(Trunk));
}
Trunk *initalize_trunk(Trunk *p, char strpassed[])
{
Trunk *tmp_trunk = create_trunk();
assert(tmp_trunk != NULL);
tmp_trunk->previous = p;
strcpy(tmp_trunk->mystr, strpassed);
return tmp_trunk;
}
// functions copied from c++ code
void show_trunks(Trunk *p)
{
if (!p)
{
return;
}
show_trunks(p->previous);
printf("%s", p->mystr);
}
void print_tree_and_trunk(Bin_Node *root, Trunk *p, bool isleft)
{
if (!root)
{
//printf("free memory here?\n");
//free(p);
return;
}
char prev_str[] = " ";
Trunk *tmp_trunk = initalize_trunk(p, prev_str); //this line added instead of new Trunk(prev, prev_str);
print_tree_and_trunk(root->left, tmp_trunk, true);
if (!p)
{
strcpy(tmp_trunk->mystr, "---");
}
else if (isleft)
{
strcpy(tmp_trunk->mystr, ".---");
strcpy(prev_str, " |");
}
else
{
strcpy(tmp_trunk->mystr, "`---");
strcpy(p->mystr, prev_str);
}
show_trunks(tmp_trunk);
printf("%d\n", root->data);
if (p)
{
strcpy(p->mystr, prev_str);
}
strcpy(tmp_trunk->mystr, " |");
print_tree_and_trunk(root->right, tmp_trunk, false);
if (!p)
{
free(tmp_trunk);
printf("free p\n");
}
}
void insert_trunk(Bin_Tree *tree)
{
Bin_Node *root = tree->root;
root = create_node();
assert(root != NULL);
root = initalize_node(root, 1);
tree->root = root;
root->left = create_node();
assert(root->left != NULL);
root->left = initalize_node(root->left, 2);
root->right = create_node();
assert(root->right != NULL);
root->right = initalize_node(root->right, 3);
root->left->left = create_node();
assert(root->left->left != NULL);
root->left->left = initalize_node(root->left->left, 4);
root->left->right = create_node();
assert(root->left->right != NULL);
root->left->right = initalize_node(root->left->right, 5);
root->right->left = create_node();
assert(root->right->left != NULL);
root->right->left = initalize_node(root->right->left, 6);
root->right->right = create_node();
assert(root->right->right != NULL);
root->right->right = initalize_node(root->right->right, 7);
}
here is the code as it stands
