Thread: building a complete binary tree

  1. #1
    Registered User
    Join Date
    Jan 2024
    Posts
    23

    building a complete binary tree

    Hello,

    I want to run a few tests on a full binary tree so I built one. It is supposed to have 3 levels, 8 leaf nodes a-h at last. My print_tree() method causes a segmentation fault. It is not because I did not use malloc() to reserve memory, I just tested it. Can someone explain why it happens?
    And what is the easiest way to build a full binary tree with the least amount of code?

    Code:
    #include <stdio.h>#include <stdlib.h>
    
    
    typedef struct Node node;
    
    
    struct Node{
      unsigned int value;
      struct Node* left;
      unsigned int left_edge : 1;
      struct Node* right;
      unsigned int right_edge : 1;
    };
    
    
    void print_tree(node* root){
      printf("%s = %d\n", "value of node ", root->value);
      if (root->left_edge != NULL){
        print_tree(root->left_edge);
      }
      if (root->right_edge != NULL){
        print_tree(root->right_edge);
      }
    
    
    }
    
    
    int main(){
    
    
      node a = {1,NULL,NULL};
      node b = {2,NULL,NULL};
      node c = {3,NULL,NULL};
      node d = {4,NULL,NULL};
      node e = {5,NULL,NULL};
      node f = {6,NULL,NULL};
      node g = {7,NULL,NULL};
      node h = {8,NULL,NULL};
    
    
      node inner_3 = {0, &a, &b, 0, 1};
      node inner_4 = {0, &c, &d, 1, 0};
      node inner_5 = {0, &e, &f, 1, 0};
      node inner_6 = {0, &g, &h, 1, 0};
    
    
      node inner_2 = {0, &inner_5, &inner_6, 1, 0};
      node* inner_1 = malloc(sizeof(node));
      inner_1->value = 2;
      inner_1->left_edge = &inner_3;
      inner_1->right_edge = &inner_4;
      inner_1->left_edge = 1;
      node root = {0, &inner_1, &inner_2, 0, 1};
    
    
      print_tree(&root);
    
    
      return 0;
    
    
    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,661
    Yeah, the first thing is fix ALL the warnings before you even try and run any more code.
    Code:
    $ gcc -Wall foo.c
    foo.c: In function ‘print_tree’:
    foo.c:19:23: warning: comparison between pointer and integer
       19 |   if (root->left_edge != NULL){
          |                       ^~
    foo.c:20:20: warning: passing argument 1 of ‘print_tree’ makes pointer from integer without a cast [-Wint-conversion]
       20 |     print_tree(root->left_edge);
          |                ~~~~^~~~~~~~~~~
          |                    |
          |                    unsigned char:1
    foo.c:17:23: note: expected ‘node *’ {aka ‘struct Node *’} but argument is of type ‘unsigned char:1’
       17 | void print_tree(node* root){
          |                 ~~~~~~^~~~
    foo.c:22:24: warning: comparison between pointer and integer
       22 |   if (root->right_edge != NULL){
          |                        ^~
    foo.c:23:20: warning: passing argument 1 of ‘print_tree’ makes pointer from integer without a cast [-Wint-conversion]
       23 |     print_tree(root->right_edge);
          |                ~~~~^~~~~~~~~~~~
          |                    |
          |                    unsigned char:1
    foo.c:17:23: note: expected ‘node *’ {aka ‘struct Node *’} but argument is of type ‘unsigned char:1’
       17 | void print_tree(node* root){
          |                 ~~~~~~^~~~
    foo.c: In function ‘main’:
    foo.c:33:20: warning: initialization of ‘unsigned char:1’ from ‘void *’ makes integer from pointer without a cast [-Wint-conversion]
       33 |   node a = {1,NULL,NULL};
          |                    ^~~~
    foo.c:33:20: note: (near initialization for ‘a.left_edge’)
    foo.c:34:20: warning: initialization of ‘unsigned char:1’ from ‘void *’ makes integer from pointer without a cast [-Wint-conversion]
       34 |   node b = {2,NULL,NULL};
          |                    ^~~~
    foo.c:34:20: note: (near initialization for ‘b.left_edge’)
    foo.c:35:20: warning: initialization of ‘unsigned char:1’ from ‘void *’ makes integer from pointer without a cast [-Wint-conversion]
       35 |   node c = {3,NULL,NULL};
          |                    ^~~~
    foo.c:35:20: note: (near initialization for ‘c.left_edge’)
    foo.c:36:20: warning: initialization of ‘unsigned char:1’ from ‘void *’ makes integer from pointer without a cast [-Wint-conversion]
       36 |   node d = {4,NULL,NULL};
          |                    ^~~~
    foo.c:36:20: note: (near initialization for ‘d.left_edge’)
    foo.c:37:20: warning: initialization of ‘unsigned char:1’ from ‘void *’ makes integer from pointer without a cast [-Wint-conversion]
       37 |   node e = {5,NULL,NULL};
          |                    ^~~~
    foo.c:37:20: note: (near initialization for ‘e.left_edge’)
    foo.c:38:20: warning: initialization of ‘unsigned char:1’ from ‘void *’ makes integer from pointer without a cast [-Wint-conversion]
       38 |   node f = {6,NULL,NULL};
          |                    ^~~~
    foo.c:38:20: note: (near initialization for ‘f.left_edge’)
    foo.c:39:20: warning: initialization of ‘unsigned char:1’ from ‘void *’ makes integer from pointer without a cast [-Wint-conversion]
       39 |   node g = {7,NULL,NULL};
          |                    ^~~~
    foo.c:39:20: note: (near initialization for ‘g.left_edge’)
    foo.c:40:20: warning: initialization of ‘unsigned char:1’ from ‘void *’ makes integer from pointer without a cast [-Wint-conversion]
       40 |   node h = {8,NULL,NULL};
          |                    ^~~~
    foo.c:40:20: note: (near initialization for ‘h.left_edge’)
    foo.c:43:26: warning: initialization of ‘unsigned char:1’ from ‘node *’ {aka ‘struct Node *’} makes integer from pointer without a cast [-Wint-conversion]
       43 |   node inner_3 = {0, &a, &b, 0, 1};
          |                          ^
    foo.c:43:26: note: (near initialization for ‘inner_3.left_edge’)
    foo.c:44:26: warning: initialization of ‘unsigned char:1’ from ‘node *’ {aka ‘struct Node *’} makes integer from pointer without a cast [-Wint-conversion]
       44 |   node inner_4 = {0, &c, &d, 1, 0};
          |                          ^
    foo.c:44:26: note: (near initialization for ‘inner_4.left_edge’)
    foo.c:44:30: warning: initialization of ‘struct Node *’ from ‘int’ makes pointer from integer without a cast [-Wint-conversion]
       44 |   node inner_4 = {0, &c, &d, 1, 0};
          |                              ^
    foo.c:44:30: note: (near initialization for ‘inner_4.right’)
    foo.c:45:26: warning: initialization of ‘unsigned char:1’ from ‘node *’ {aka ‘struct Node *’} makes integer from pointer without a cast [-Wint-conversion]
       45 |   node inner_5 = {0, &e, &f, 1, 0};
          |                          ^
    foo.c:45:26: note: (near initialization for ‘inner_5.left_edge’)
    foo.c:45:30: warning: initialization of ‘struct Node *’ from ‘int’ makes pointer from integer without a cast [-Wint-conversion]
       45 |   node inner_5 = {0, &e, &f, 1, 0};
          |                              ^
    foo.c:45:30: note: (near initialization for ‘inner_5.right’)
    foo.c:46:26: warning: initialization of ‘unsigned char:1’ from ‘node *’ {aka ‘struct Node *’} makes integer from pointer without a cast [-Wint-conversion]
       46 |   node inner_6 = {0, &g, &h, 1, 0};
          |                          ^
    foo.c:46:26: note: (near initialization for ‘inner_6.left_edge’)
    foo.c:46:30: warning: initialization of ‘struct Node *’ from ‘int’ makes pointer from integer without a cast [-Wint-conversion]
       46 |   node inner_6 = {0, &g, &h, 1, 0};
          |                              ^
    foo.c:46:30: note: (near initialization for ‘inner_6.right’)
    foo.c:49:32: warning: initialization of ‘unsigned char:1’ from ‘node *’ {aka ‘struct Node *’} makes integer from pointer without a cast [-Wint-conversion]
       49 |   node inner_2 = {0, &inner_5, &inner_6, 1, 0};
          |                                ^
    foo.c:49:32: note: (near initialization for ‘inner_2.left_edge’)
    foo.c:49:42: warning: initialization of ‘struct Node *’ from ‘int’ makes pointer from integer without a cast [-Wint-conversion]
       49 |   node inner_2 = {0, &inner_5, &inner_6, 1, 0};
          |                                          ^
    foo.c:49:42: note: (near initialization for ‘inner_2.right’)
    foo.c:52:22: warning: assignment to ‘unsigned char:1’ from ‘node *’ {aka ‘struct Node *’} makes integer from pointer without a cast [-Wint-conversion]
       52 |   inner_1->left_edge = &inner_3;
          |                      ^
    foo.c:53:23: warning: assignment to ‘unsigned char:1’ from ‘node *’ {aka ‘struct Node *’} makes integer from pointer without a cast [-Wint-conversion]
       53 |   inner_1->right_edge = &inner_4;
          |                       ^
    foo.c:55:19: warning: initialization of ‘struct Node *’ from incompatible pointer type ‘node **’ {aka ‘struct Node **’} [-Wincompatible-pointer-types]
       55 |   node root = {0, &inner_1, &inner_2, 0, 1};
          |                   ^
    foo.c:55:19: note: (near initialization for ‘root.left’)
    foo.c:55:29: warning: initialization of ‘unsigned char:1’ from ‘node *’ {aka ‘struct Node *’} makes integer from pointer without a cast [-Wint-conversion]
       55 |   node root = {0, &inner_1, &inner_2, 0, 1};
          |                             ^
    foo.c:55:29: note: (near initialization for ‘root.left_edge’)
    That left_edge / right_edge stuff is complete junk, it needs to go.
    You only need the left and right pointers.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Jan 2024
    Posts
    23
    thanks for your reply. The left and right_edge fields are for the tests I want to do, they do not have anything to do with a normal tree structure. Will I still need to fix the warnings?

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,661
    > Will I still need to fix the warnings?
    Yes, absolutely, always!

    Because you're trying to use those 'edge' fields, which are only 1-bit integers as pointers.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Jan 2024
    Posts
    23
    I fixed everything and printing works now. do you have any idea why segault came?
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    
    #define on 1
    #define off 0
    
    
    typedef struct Node node;
    
    
    struct Node{
      unsigned int value;
      struct Node* left;
      unsigned int left_edge : 1;
      struct Node* right;
      unsigned int right_edge : 1;
    };
    
    
    void print_tree(node* root){
      printf("%s = %d\n", "value of node ", root->value);
      if (root->left != NULL){
        print_tree(root->left);
      }
      if (root->right != NULL){
        print_tree(root->right);
      }
    
    
    }
    
    
    int main(){
    
    
      node a = {1,NULL,0,NULL,0};
      node b = {2,NULL,0,NULL,0};
      node c = {3,NULL,0,NULL,0};
      node d = {4,NULL,0,NULL,0};
      node e = {5,NULL,0,NULL,0};
      node f = {6,NULL,0,NULL,0};
      node g = {7,NULL,0,NULL,0};
      node h = {8,NULL,0,NULL,0};
    
    
      node inner_3 = {0, &a, 0, &b, 1};
      node inner_4 = {0, &c, 1, &c, 0};
      node inner_5 = {0, &e, 1, &f, 0};
      node inner_6 = {0, &g, 1, &h, 0};
    
    
      node inner_2 = {0, &inner_5, 1, &inner_6, 0};
      // the error does not occur because I did not reserve space for the object with malloc.
      node* inner_1 = malloc(sizeof(node));
      inner_1->value = 2;
      inner_1->left = &inner_3;
      inner_1->right = &inner_4;
      inner_1->left_edge = 1;
      node root = {0, inner_1, 0, &inner_2, 1};
    
    
      print_tree(&root);
    
    
      return 0;
    
    
    }

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,661
    > do you have any idea why segault came?
    Yeah, trying to use a 1-bit value as a pointer.

    Simply caused by you ignoring the warnings before you tried to run it.

    Which is either 0 (aka a NULL pointer) or 1 (next door to NULL).

    Most operating systems are going to blackout the first several megabytes of the virtual address space at least, so that any plausible mis-use of a NULL pointer (whether as *p, p[n] or p->member) is going to cause a fault and your program to end.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    Registered User
    Join Date
    Dec 2017
    Posts
    1,633
    You are still ignoring one warning (unused variable d).

    Also, this is a strange comment:

    // the error does not occur because I did not reserve space for the object with malloc.
    Why do you malloc one random node when you store all the others on the stack?
    You could just say:
    Code:
      node inner_1 = {2, &inner_3, 1, &inner_4, 0};
    (I don't understand why inner_1's value would be 2 when all the other inner nodes are 0.)

    I'm not sure what you mean by "edge", but if you mean left child or right child, then you aren't setting them correctly.
    Code:
    .                     root
               i1                      i2
         i3          i4          i5          i6
       a    b      c    d      e    f      g    h
    If you do mean left and right child, another possibility is to use a parent pointer.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Node{
      int value;
      struct Node* left, *right, *parent;
    } Node;
    
    void print_tree(Node* node){
      if (node) {
        printf("%d ", node->value);
        if (node->parent)
          if (node->parent->left == node)
            printf("left");
          else
            printf("right");
        else
          printf("root");
        putchar('\n');
        print_tree(node->left);
        print_tree(node->right);
      }
    }
    
    int main(){
      Node a = {1, NULL, NULL, NULL};
      Node b = {2, NULL, NULL, NULL};
      Node c = {3, NULL, NULL, NULL};
      Node d = {4, NULL, NULL, NULL};
      Node e = {5, NULL, NULL, NULL};
      Node f = {6, NULL, NULL, NULL};
      Node g = {7, NULL, NULL, NULL};
      Node h = {8, NULL, NULL, NULL};
    
      Node inner_3 = {0, &a, &b, NULL};
      Node inner_4 = {0, &c, &d, NULL};
      Node inner_5 = {0, &e, &f, NULL};
      Node inner_6 = {0, &g, &h, NULL};
    
      a.parent = b.parent = &inner_3;
      c.parent = d.parent = &inner_4;
      e.parent = f.parent = &inner_5;
      g.parent = h.parent = &inner_6;
    
      Node inner_1 = {0, &inner_3, &inner_4, NULL};
      Node inner_2 = {0, &inner_5, &inner_6, NULL};
    
      inner_3.parent = inner_4.parent = &inner_1;
      inner_5.parent = inner_6.parent = &inner_2;
    
      Node root = {0, &inner_1, &inner_2, NULL};
    
      inner_1.parent = inner_2.parent = &root; 
    
      print_tree(&root);
    
      return 0;
    }
    A little inaccuracy saves tons of explanation. - H.H. Munro

  8. #8
    Registered User
    Join Date
    Apr 2021
    Posts
    140
    Quote Originally Posted by john_12 View Post
    And what is the easiest way to build a full binary tree with the least amount of code?
    Just put the data in as initializers.

    Code:
        struct Node {
            struct Node *left;
            struct Node *right;
            char payload;
            };
    
        struct Node * Tree_root = &(struct Node){
            .payload='D',
            .left = &(struct Node){
                .payload='B',
                .left=&(struct Node){.payload='A' },
                .right=&(struct Node){.payload='C'},
                },
            .right = &(struct Node) {
                .payload='F',
                .left=&(struct Node){.payload='E' },
                .right=&(struct Node){.payload='G'},
                },
            }

  9. #9
    Registered User
    Join Date
    Dec 2017
    Posts
    1,633
    This is even less code:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Tree {
        int value;
        struct Tree *left, *right;
    } Tree;
    
    void treePrint(Tree *node, int depth) {
        if (!node) return;
        if (node->right) treePrint(node->right, depth + 1);
        printf("%*s%2d\n", depth * 4, "", node->value);
        if (node->left) treePrint(node->left, depth + 1);
    }
    
    void treeAdd(Tree **node, int value) {
        if (!*node) {
            *node = malloc(sizeof **node);
            (*node)->value = value;
            (*node)->left = (*node)->right = NULL;
        }
        else if (value < (*node)->value)
            treeAdd(&(*node)->left, value);
        else
            treeAdd(&(*node)->right, value);
    }
    
    int main() {
        Tree *root = NULL;
    /*
                   8
           4              12 
       2       6      10      14
     1   3   5   7   9  11  13  15
    */
        int values[] = { 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 };
    
        for (int i = 0; i < 15; ++i)
            treeAdd(&root, values[i]);
    
        treePrint(root, 0);
    
        return 0;
    }
    A little inaccuracy saves tons of explanation. - H.H. Munro

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. leafs of binary complete tree
    By RyanC in forum C Programming
    Replies: 7
    Last Post: 12-30-2018, 04:25 PM
  2. check if binary tree is complete
    By telmo_d in forum C Programming
    Replies: 0
    Last Post: 11-21-2015, 09:14 AM
  3. Building Binary Tree
    By 7heavens in forum C++ Programming
    Replies: 1
    Last Post: 04-18-2010, 01:27 PM
  4. binary tree complete check
    By ichijoji in forum C++ Programming
    Replies: 5
    Last Post: 11-12-2004, 05:48 PM
  5. Building a Binary Search Tree off sorted data
    By BlackCitan in forum C Programming
    Replies: 0
    Last Post: 12-01-2003, 09:52 PM

Tags for this Thread