i have broken my code down a little so it is more manageable
header:
Code:
#ifndef BST_H_INCLUDED
#define BST_H_INCLUDED
#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[]);
// copied from c++ code
void show_trunks(Trunk *p);
void print_tree_and_trunk(Bin_Node *root, Trunk *p, bool isleft);
#endif // BST_H_INCLUDED
i have added some printf statements in the print tree function to get the address of the node and its children's address's lines 69 and 70 of the following code
Code:
#include "bst.h"
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
{
//printf("the value of nodes root = %d the address of node root = %p\n",(*root)->data, &(*root));
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("\nnode data = %d node address = %p\n", root->data, &root);
printf("node left = %p node right = %p\n", root->left, root->right);
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;
//printf("tree->root = %p\n", tree->root);
}
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 (tmp_trunk)
{
free(tmp_trunk);
}
}
and lastly main
Code:
#include "bst.h"
void insert_trunk(Bin_Tree *tree);
int main()
{ //10,6, 3, 9, 2, 3, 13, 54, 20, 43
int i, nums[] = {1, 2, 3};
Bin_Tree *tree;//, *tree_trunk;
tree = create_tree();
for (i = 0; i < 3; 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;
}
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);
//*/
}
if i run this i get the following out put
Code:
node data = 1 node address = 0x7ffc6249a268
node left = (nil) node right = 0x5630434472a0
node data = 2 node address = 0x7ffc6249a248
node left = (nil) node right = 0x5630434472c0
node data = 3 node address = 0x7ffc6249a228
node left = (nil) node right = (nil)
searching right child of 2
searching right child of 1
---1
`---2
`---3
there are 3 nodes in the tree
node deleated
node deleated
node deleated
Process returned 0 (0x0) execution time : 0.001 s
Press ENTER to continue.
the output doesn't make any sense to me as the tree is obviously connected together yet the address's (if i have got them correctly ) are different to the left/right pointers of the node above. ie suppose the node with the data of 2 right pointer points to x then the address of the node with the data of 3 should be x
coop