ok this is weird. i went back to the code in post 65 copied and pasted in the insert_node code so exactly as it was when it was falling over and crying in the corner. went to compile it so its all saved and it threw a warning about implicit deceleration of function count levels so muttering all sorts of things under my breath about what now etc etc.... i added the function prototype to the header file and removed it from main. it then gave warnings about the arguments being passed so removed the & and f me it worked as it should i get the right results. Why the bloody hell it didn't throw out the warnings the first time i don't know. its done this to me before. something missing or extra but it doesn't see the issue then cut and paste it back in and 5000 alarm bells ring.
all source code below
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;
int balance_factor;
int height;
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);
int countlevels(Bin_Node *node);
// 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
bstlib:
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->balance_factor = 0;
node->height = 0;
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;
(*root)->balance_factor = 0;
return true;
}
else
{
//printf("the value of the node = %d the value of nodes root = %d the address of node root = %p\n", node->data, (*root)->data, *root);
node->height++;
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
{
if (insert_node(&(*root)->right, node))
{
(*root)->balance_factor = countlevels((*root)->left) - countlevels((*root)->right);
return true;
}
}
else if ((*root)->data != node->data)
{
if (insert_node(&(*root)->left, node))
{
(*root)->balance_factor = countlevels((*root)->left) - countlevels((*root)->right);
return true;
}
}
}
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 (%d)\n", root->data, root->balance_factor);
//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 deleted\n");
}
}
void insert(Bin_Tree *tree, int node_data)
{
Bin_Node *node;
node = create_node();
assert(node != NULL);
node = initalize_node(node, node_data);
if (!insert_node(&tree->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;
//printf("address of the root is %p\n", 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);
free(tree);
tree = NULL;
}
// 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);
//printf("%d A:%p L:%p R:%p\n", root->data, (void *)root, (void *)root->left, (void *)root->right);
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);
}
}
main
Code:
#include "bst.h"
void insert_trunk(Bin_Tree *tree);
void slr(Bin_Node **root, Bin_Node *node); //root is the one pointing at the troubled node, node is the troubled node
void srr(Bin_Node **root, Bin_Node *node);
//int countlevels(Bin_Node *node);
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);
//slr(&tree->root, tree->root);
//print(tree);
//srr(&tree->root, tree->root);
//slr(&tree->root->right, tree->root->right);
//srr(&tree->root, tree->root);
//print(tree);
destroy(tree);
//tree_trunk = create_tree();
//insert_trunk(tree_trunk);
//print(tree_trunk);
//destroy(tree_trunk);
assert(tree != NULL);
//free(tree_trunk);
return 0;
}
void slr(Bin_Node **root, Bin_Node *node)
{
Bin_Node *A = node;
Bin_Node *B = A->right;
Bin_Node *C = B->left;
B->left = A;
*root = B;
/*
if (C)
{
A->right = C; //if B has a left child set A->right to point to it as it must be larger than A otherwise it would
} //of been on A's left.
else
{
A->right = NULL; //no left child for B so set A->right to null;
}
//*/
A->right = C;
//assert(A->right != NULL);
}
void srr(Bin_Node **root, Bin_Node *node)
{
Bin_Node *A = node;
Bin_Node *B = A->left;
Bin_Node *C = B->right;
B->right = A;
*root = B;
A->left = C;
}
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);
//*/
}
int countlevels(Bin_Node *node)
{
int x = 0;
if (!node)
{
return 1;
}
x += countlevels(node->left);
x += countlevels(node->right);
return x;
}
coop