Thread: printing tree trunk

  1. #1
    Registered User
    Join Date
    Apr 2019
    Posts
    808

    printing tree trunk

    i have tried to alter the code here Print Binary Tree Structure with its contents in C++ - Techie Delight to c and incorporate it in my bst.
    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[]);
    
    // 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 = create_tree();
        for (i = 0; i < 10; i++)
        {
            insert(tree, nums[i]);
        }
        print(tree);
        destroy(tree);
    
        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 = p;
    
        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)
        {
            return;
        }
    
        char prev_str[] = "    ";
        Trunk *tmp_trunk = create_trunk();          //
        assert(tmp_trunk != NULL);                         //these lines added instead of new Trunk(prev, prev_str);
        tmp_trunk = initalize_trunk(p, 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);
    }
    the issue arrises with the initallize trunk function the argument p passed in is null when dealing with the root of the whole tree as there is obviously no previous node.

    origonaly i tried setting tmp_trunk to null at decleration then when that threw a segmentation fault. I remembered i had mistakenly done that before when i was doing lists so i set it to p as in the above code but still get the same issue. because i assume in the first itteration p = null.

    there are two other issues with this code.
    1) how do i free the memory allocated for the trunk...as i assume this will be called several times.
    2)when i tried to debugg (its how i discovered where the issue was) i have somthing called _PRETTY_FUNCTION_ with the function name print_tree_and_trunk what is this?

    many thanks
    coop

  2. #2
    Registered User
    Join Date
    Apr 2019
    Posts
    808
    ok i got it working by calling create trunk from inside initalize trunk. bit of a cop out i know but best i could do then at least its starting off with a non null pointer
    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);
    
        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)
        {
            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);
    }
    
    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);
    }
    i added the function insert_trunk so i could compaire my results with the one on the website.
    coop

  3. #3
    Registered User
    Join Date
    May 2019
    Posts
    214
    @cooper1200

    You've been at this long enough that you're talking to yourself, aren't you?

    Been there. Done that.

    BTW, I tried it with a change to the insert loop to stuff random number (rand() ), with 350 entries.

    This thing works!
    Last edited by Niccolo; 06-12-2019 at 09:36 AM.

  4. #4
    Registered User
    Join Date
    Apr 2019
    Posts
    808
    how and where do i free the nodes though?

  5. #5
    Registered User
    Join Date
    May 2019
    Posts
    214
    Just looking into this now....question first, though....what compiler/operating system are you using?

  6. #6
    Registered User
    Join Date
    May 2019
    Posts
    214
    I've had a "dickens" of a time here.....I've been searching for what I read as "initialize_trunk", but it's spelled "initalize_trunk". I thought my editor was loosing it's mind.

    More in a moment.

    Edit: @cooper1200,

    Ok, look at "print_tree_and_trunk".

    That is where you create a tmp_trunk. That's what needs deletion. Within that function you allocate the tmp_trunk, but when that function returns, you're going to lose contact with that.

    Now, in initalize_trunk (I've not changed your code yet ), you take in p and set the new tmp_trunk's previous member to it. That's probably from c++ source.

    Ok, so there's a single linked list being developed.

    Yet, when all of this finishes the recursive calls to print the tree, execution returns to that first call to print_tree_and_trunk, where the incoming p was null (from the initial caller).

    Once THAT returns, the tmp_trunk fashioned there falls out of scope, but has not yet deleted all the nodes the link list developed. That's a memory link of the entire chain.

    This is the same "chicken-and-egg" paradox you faced with creating the tree in the first place. Here, however, you have nothing representing the entire trunk structure (it was probably an owning class in the C++ source, and that probably deleted the tree automatically upon destruction).

    Now, however, you must sense when returning from print_tree_and_trunk that this is the upper most call of the recursion, where p is null.

    At that point, you need to arrange to delete the tmp_trunk, and recurse through it's single linked list to delete the nodes throughout.

    Also, elsewhere, when you call create_tree, that Bin_Tree is never deleted. You do go through and delete all the nodes IN the tree, but those are the Bin_Nodes in the tree. You're not deleting the Bin_Tree itself.

    I noticed that using Visual Studio 2019, implementing the memory debug feature. That's why I asked what compiler/os you're using. You'll want to enable some kind of memory debug instrument here to ensure you're not missing something.

    For Visual Studio C/C++, one defines _CRTDBG_MAP_ALLOC before including "stdlib.h". Then, include "crtdbg.h", and at the exit of the program call _CrtDumpMemoryLeaks() to get the report.
    Last edited by Niccolo; 06-12-2019 at 03:49 PM.

  7. #7
    Registered User
    Join Date
    Apr 2019
    Posts
    808
    well in about 10 minuets i will be on Linux permanently windows has quite literally left via the window... its annoyed me once too often (doesn't take much these days)

  8. #8
    Registered User
    Join Date
    Apr 2019
    Posts
    808
    in answer to your question i am on linux mint using codeblocks ide

  9. #9
    Registered User
    Join Date
    May 2019
    Posts
    214


    Oh, my...yes, we all have a hate/love(sortof) relationship with Windows.

    You'll have to search the Internet for the means to implement memory tracking in debug builds on whatever tools you install for development on Linux.

    The few things that keep me on Windows are applications like 3DS Max, Maya, AutoCAD, Inventor, Photoshop, Illustrator, and....Visual Studio.

    I've tried lots of IDE's. I've never found one that actually outdoes Visual Studio through all the versions going back to 4.2, when Windows 95 was new.

    Though, Borland's line was good for a while.

    At any one moment I'll have 3 to 5 operating systems running in VM's, at least two will be a Linux distro (Xubuntu at the moment). I disable TCP/IP in Windows, so the host (Windows 8.1) can't touch the Internet unless I turn that on (rarely). Only the VM's touch the 'net, and almost always from Linux.

    Linux file system(s) (you have many to choose from) are vastly superior to Windows. Performance, reliability...everything about the Linux filesystem (and the layers of the os that service it) are superior. It is one of the unspoken Achilles Heals of Windows. I've had Windows "Blue Screen" because a CD/DVD had a bad block while trying to run an executable from that drive (never did that again).

    It can still happen on USB flash drives when running code from there.

    Never on Linux. The process can crash, not the entire OS.

    The world would be better off if everyone moved to Linux (MAC is UNIX, so I'd argue that's ok), and left Windows to history.

    It's just that software I require which won't run as well in a VM. Visual Studio, however, will run well in a VM of Windows.

    ...and it can target Linux.

  10. #10
    Registered User
    Join Date
    Apr 2019
    Posts
    808
    i had linux in a vm on a win 10 host.... however today it decided to crash and when i restarted it it used an outdated file and ive lost 50% of my code etc etc... (friend said he could hear me swearing from 10 miles away) so i as going to have a dual boot then discovered on searching what combination of keys to press to get into bios to boot from a usb that windows can access that too so its over the rail.

    the latest news i heard was that microsoft were going to stop selling windows and licence it for a year then when the year was up you had to pay again. so its days were numbered anyway

  11. #11
    Registered User
    Join Date
    May 2019
    Posts
    214
    (working backwards)....I had the impression that was what Windows 10 was all about. Annual fees. Free to get 'em hooked. Over 1/3rd of the user base is still on Windows 7 anyway. Many on Windows 10 either got it with a new computer, or can't really explain how it happened to them

    Linux on host, Windows on a VM - good recipe.


    Ouch! 50%!?!

    Ok, here's the other thing about that.....

    ...I'm sure you've considered it, and I've consulted for decades for professionals (architects, engineers - pro users but not always programmers/CS engineers) who rely on their machines daily, but never back the f up.

    I made a friend for life back in the late 90's over this. This architect was working late, on NT 4/Windows 2000. Accidentally he deleted the root directory of the company's entire architectural drawing server (where there's no recycle bin in Windows to help). He called me on my cell (the last cell I've ever owned), absolutely scared for his job. The entire company had been erased (his words).

    When I made it to the office about 30 minutes later (traffic here is really awful, it would have been 10 minutes off rush hour), he was literally shaking, pacing, talking to himself.

    Barely two weeks before this I started consulting for this firm, and among the first things I did was to setup an automated backup facility on their server. Every file save was preserved, but of course only the firm's owner was even aware.

    I was able to restore the directory, which contained every drawing file they'd worked on in the last 5 years (for a firm of 25 architects). This included the files he had just finished work on, late (he was the only one left in the office that night).

    It took that old hardware (new at the time) about 2 hours to restore everything. It was about 3 Gbytes, which at that time was considered huge.

    20 years later, he's still a BFF - at least among those I've met through professional means.

    Best of luck. That sucks.

  12. #12
    Registered User
    Join Date
    Apr 2019
    Posts
    808
    why didnt i take a snapshot or back the f up was pretty much what was being shouted lol

    the friend i mentioned runs several flavours of bsd and linux....with windows on a vm that "DOES NOT HAVE INTERNET" (polite version of his words) only time it gets internet is hen he gets one of the calls from microsoft.... then its thier turn to swear and he just restores back to a snap shot but thats another story

    back to the issue at hand i have installed valgrind and sure enough it found a memory leak soon as i added free(tree) to main on the origonal code from yesterday iit was fine

  13. #13
    Registered User
    Join Date
    May 2019
    Posts
    214
    That's what I was trying to remember.....valgrind. Good stuff - now that I've been reminded.

  14. #14
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    Your memory leak is due to never freeing the "Trunk" linked list. Here's a rewrite/simplification of your code. Note that it frees the most recent "Trunk" before popping up the recursive stack. I've renamed some stuff like "Trunk" to "Branch" since that made more sense to me. I also flipped the tree over since it looks more natural to me with the left side on the bottom.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include <string.h>
    #include <time.h>
     
    typedef struct Node {
        int value;
        struct Node *left, *right;
    } Node;
     
    typedef struct Tree {
        Node *root;
        int   size;
    } Tree;
     
    typedef struct Branch {
        struct Branch *prev;
        const char    *str;
    } Branch;
     
    Tree*   create_tree      ();
    Node*   create_node      (int value);
    void    destroy_tree     (Tree *root);
    void    destroy_tree_rec (Node *node);
    void    insert           (Tree  *tree, int value);
    bool    insert_rec       (Node **node, int value);
    void    print            (const Tree *tree);
    void    print_rec        (const Node *node);
    void    print_tree       (const Tree *tree);
    void    print_tree_rec   (const Node *node, const Node *prev,
                              Branch *prevBranch);
    Branch* create_branch    (Branch *prev, const char *str);
    void    print_branches   (Branch *p);
    void*   xmalloc          (size_t sz);
     
    int main() {
        Tree *tree = create_tree();
    #if 1
        int nums[] = {10, 6, 3, 9, 2, 13, 54, 20, 43, 60};
        for (size_t i = 0; i < sizeof nums / sizeof *nums; i++)
            insert(tree, nums[i]);
    #else
        srand(time(0));
        for (int i = 0; i < 50; ++i) insert(tree, rand() % 100);
    #endif
        print(tree);
        print_tree(tree);
        destroy_tree(tree);
        return 0;
    }
     
    void *xmalloc(size_t sz) {
        void *p = malloc(sz);
        if (!p) {
            perror("xmalloc");
            exit(EXIT_FAILURE);
        }
        return p;
    }
     
    Tree *create_tree() {
        Tree *tree = xmalloc(sizeof *tree);
        tree->size = 0;
        tree->root = NULL;
        return tree;
    }
     
    Node *create_node(int value) {
        Node *node = xmalloc(sizeof *node);
        node->value = value;
        node->left = node->right = NULL;
        return node;
    }
     
    void insert(Tree *tree, int value) {
        if (insert_rec(&tree->root, value))
            tree->size++;
    }
     
    bool insert_rec(Node **root, int value) {
        if (!*root) {
            *root = create_node(value);
            return true;
        }
        if ((*root)->value < value)
            return insert_rec(&(*root)->right, value);
        if ((*root)->value != value)
            return insert_rec(&(*root)->left, value);
        return false; // the node already exists
    }
     
    void print(const Tree *tree) {
        print_rec(tree->root);
        putchar('\n');
    }
     
    void print_rec(const Node *node) {
        if (!node) return;
        print_rec(node->left);
        printf("%d ", node->value);
        print_rec(node->right);
    }
     
    void destroy_tree(Tree *tree) {
        destroy_tree_rec(tree->root);
        free(tree);
    }
     
    void destroy_tree_rec(Node *root) {
        if (root) {
            destroy_tree_rec(root->left);
            destroy_tree_rec(root->right);
            free(root);
        }
    }
     
    void print_tree(const Tree *tree) {
        print_tree_rec(tree->root, NULL, NULL);
    }
     
    void print_tree_rec(const Node *node, const Node *prev,
                        Branch *prevBranch) {
     
        static const char *Blank = "    ",
                          *Bar   = "   |",
                          *Right = ".---",
                          *Left  = "`---",
                          *Root  = "----";
     
        if (!node) return;
     
        Branch *branch = create_branch(prevBranch, Blank);
     
        print_tree_rec(node->right, node, branch);
     
        if (!prev)
            branch->str = Root;
        else if (node == prev->left) {
            branch->str = Left;
            prevBranch->str = Blank;
        }
        else
            branch->str = Right;
     
        print_branches(branch);
        printf("%d\n", node->value);
     
        if (prev) prevBranch->str = (node == prev->left ? Blank : Bar);
        branch->str = Bar;
     
        print_tree_rec(node->left, node, branch);
     
        free(branch);
    }
     
    Branch *create_branch(Branch *prev, const char *str) {
        Branch * branch = xmalloc(sizeof *branch);
        branch->prev = prev;
        branch->str = str;
        return branch;
    }
     
    void print_branches(Branch *branch) {
        if (!branch) return;
        print_branches(branch->prev);
        printf("%s", branch->str);
    }
     
    void delete_branches(Branch *branch) {
        for (Branch *prev; branch; branch = prev) {
            prev = branch->prev;
            free(branch);
        }
    }
    A little inaccuracy saves tons of explanation. - H.H. Munro

  15. #15
    Registered User
    Join Date
    Apr 2019
    Posts
    808
    Code:
    ==20342== 
    ==20342== HEAP SUMMARY:
    ==20342==     in use at exit: 512 bytes in 16 blocks
    ==20342==   total heap usage: 36 allocs, 20 frees, 1,976 bytes allocated
    ==20342== 
    ==20342== LEAK SUMMARY:
    ==20342==    definitely lost: 224 bytes in 7 blocks
    ==20342==    indirectly lost: 288 bytes in 9 blocks
    ==20342==      possibly lost: 0 bytes in 0 blocks
    ==20342==    still reachable: 0 bytes in 0 blocks
    ==20342==         suppressed: 0 bytes in 0 blocks
    ==20342== Rerun with --leak-check=full to see details of leaked memory
    ==20342== 
    ==20342== For lists of detected and suppressed errors, rerun with: -s
    ==20342== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
    this is the report for the above code i just don't know where to free it. i tried doing it above the return line 224 in the if statement but that didn't work. and as every time the function gets passed that point i assign a new lot of memory to it its lost

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Printing a Binary Tree:
    By jocdrew21 in forum C++ Programming
    Replies: 5
    Last Post: 02-01-2014, 10:06 PM
  2. need help with printing out a tree
    By winggx in forum C Programming
    Replies: 7
    Last Post: 03-03-2010, 01:42 AM
  3. Binary Tree Printing
    By ss3x in forum C++ Programming
    Replies: 0
    Last Post: 02-26-2002, 12:25 AM
  4. FAQ Printing a binary tree?? (C)
    By Unregistered in forum FAQ Board
    Replies: 5
    Last Post: 10-31-2001, 07:35 PM
  5. Printing a binary tree??
    By Unregistered in forum C Programming
    Replies: 5
    Last Post: 10-31-2001, 07:35 PM

Tags for this Thread