Thread: memmory addresses not working out or me screwing somthing up

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

thank you. i read in the book the other day that anyone who understand pointers loves c anyone who doesn't understand pointers hates c and is wasting their time. i just cant seem to get my head around when to use which version. I had this issue in my maths a level. there were a couple of things i just couldn't grasp we spent ages on them and no matter what i tried i always came up with the wrong answer. in the end we had to leave it and just hope it didn't come up in the exam

im confusing myself now i have changed 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->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 the node = %d the value of nodes root = %d the address of node root = %p\n", node->data, (*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;

    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);
}

// 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);
    }
}

i have un-commented line 43 and added in the value of the node to be added into the tree and un-commented line 109.

i get the following output

Code:

tree->root = 0x564a9c6d2280
the value of the node = 2 the value of nodes root = 1 the address of node root = 0x564a9c6d2280
the value of the node = 3 the value of nodes root = 1 the address of node root = 0x564a9c6d2280
the value of the node = 3 the value of nodes root = 2 the address of node root = 0x564a9c6d26b0
address of the root is 0x564a9c6d2280

node data = 1 node address = 0x564a9c6d2280
node left = (nil) node right = 0x564a9c6d26b0

node data = 2 node address = 0x564a9c6d26b0
node left = (nil) node right = 0x564a9c6d26d0

node data = 3 node address = 0x564a9c6d26d0
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.

what i am trying to achieve with all these printf's is where i can put a line of code to update another member in the node struct so it knows what its parent is so when i come to do rotations i don't loose where i am.
coop

im confused because i don't seem to get the right results tree root points to the first node.... so node 1's parent should be the tree root node two's parent should be node 1 and node three's parent should be node 2 but i dont think i am getting that

im also wondering that if the addresses are correct if i can replace the printf's with node->parent (when it exists) = *root

i need to find away of assigning the parent node to the child's nodes parent pointer. the tree at the moment is unbalanced i need to do a left rotate and to do that i need to know which node is parent of which node so i dont loos track of them (i think)

No, you don't.

Seriously, unless you just want to have the parent for your own purpose, I promise you (and I've had my coffee, reviewed the material, I'm clear on this) the parent member of the node will only serve to confuse and confound.

Don't do it because you think it is the way the AVL algorithm should be implemented. It isn't.

The rotations happen from the parent's perspective, which is defined by the point of the recursion where it is performed.

Did you "get" my questions on what the stack is? Are you clear on what the stack is and how it works with recursion?

ok it looks like i am getting the parent node address or at least the results from your line match the results from mine.. trouble is with this is every time i run it i get slightly differing addresses so its hard to visualize and confirm my findings

i think the stack is last in first out and you can only work at the top level, this imaginary block is like a magazine in a rifle you can only load it from the top 1 round at a time and you can only empty it 1 round at a time. when you remove a round the ones below it are pushed up one slot (sorry for the mixed metaphore)

my understanding of recurstion is at the point of calling its self the value computed is put on the stack and so on untill it reaches its conclustion then it pops each value off the stack as it unwinds. for example

Code:

int myrecurse(int x)
{
    if (x == 3)
    {
        return x;
    }
    return x + myrecurse(x + 1)
}

if i send x = 1 into the function
x=1 gets put on the stack x now = 2
x=2 gets put on the stack x now = 3
x = 3 so return 3
get the 2 off the stack and add three to it x=5
get the 1 off the stack and add the 1 to x so x = 6
return 6

i was just working on the rotating functions for the moment. but i was thinking of having three more members in the node left height , right height and balance factor of the node (left height - right height) that can then be checked for the range -1 to 1. calculating the height of the parent of those node(s) can be calculated (i think) by adding the left height of each node together + 1 same for the right. i think the height of each node can be done recursively a little like my example above.