How to add node to binary tree in C?

Question

How do I add more nodes to my binary tree if A (left) and B (right) are already full? I just need to create a tree that is balanced. But I can't figure out how to add more data to the tree. Any help would be greatly appreciated.

Thanks in advance for any tipps.

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

struct node
{
    char *titel;
    struct node *A;
    struct node *B;
};

void display(struct node *leaf)
{
    if (leaf != NULL)
    {
        display(leaf->A);
        printf("%s\n",leaf->titel);
       display(leaf->B);
    }
}

struct node *insert(char* titel, struct node **leaf)
{
    if (*leaf == 0)
    {
        *leaf = (struct node*)malloc(sizeof(struct node));
        (*leaf)->titel = malloc(strlen(titel)+1);
        strcpy((*leaf)->titel,titel);
        (*leaf)->A = NULL;
        (*leaf)->B = NULL;
    }
    else if ((*leaf)->A == NULL)
    {
        (*leaf)->A = insert(titel,&(*leaf)->A);
    }
    else if ((*leaf)->B == NULL )
    {
        (*leaf)->B = insert(titel,&(*leaf)->B);
    }
    //WHAT TO ADD HERE TO CREATE ANOTHER NODE?
    return(*leaf);
}

int main(int argc, char const *argv[])
{
    struct node *root = NULL;
    insert("root",&root);
    insert("chapter_1A",&root);
    insert("chapter_1B",&root);
    insert("chapter_2A",&root);
    insert("chapter_2B",&root);
    insert("chapter_3A",&root);
    display(root);
    return 0;
}

Output should be like a balanced binary tree. Mustn't be printed but stored like that in memory.

Actual output:

chapter_1A
root
chapter_1B

                     root
                  /       \
            chapter_1A  chapter_1B
           /      \      /      \
         ch_2A  ch_2B  ch_3A   ch_3B
              and so on.

What's the exact problem? What output do you get and what output do you expect? — Jabberwocky
– Jabberwocky, Commented Nov 28, 2017 at 22:01
I don't know how to add another node for my tree. Thats my problem. I am creating a root node, then filling in the left hand side of the root and then the right hand side. But I don't know how to create another branch from the lefthand side node or the righthandside node. Thats my exact problem. Edit: Input can be seen in the main. Output should be the tree starting from left to right, like; root / \ ch_A1 ch_B1 / \ / \ A2 B2 A3 B3 just like a balanced binary search tree. — Gerhard Haid
– Gerhard Haid, Commented Nov 28, 2017 at 22:02
Sigh... what is the actual output of the program? And what output do you expect? Please edit your question and make that clear there. — Jabberwocky
– Jabberwocky, Commented Nov 28, 2017 at 22:05
Try to take a look at this page from wikipedia. From your code it seems that your tree is not ordered, so it can be even simpler to implement if you don't have this constraint. — Roberto Trani
– Roberto Trani, Commented Nov 28, 2017 at 22:27

davmac · Accepted Answer · 2017-11-29 01:48:28Z

3

How do I add more nodes to my binary tree if A (left) and B (right) are already full?

By "full" I take it that you mean both child nodes themselves have two children. In this case, any new node must be added to one of the children of the children. Typically you would do this via a recursive function, so that it correctly handles the case when the children's children are also "full", and so on.

I just need to create a tree that is balanced

(Note that "balanced" can itself mean several things. For instance, there are "height balanced" and "weight balanced" trees. You don't specify which you want).

The question then is which (full) child to add a new node to - right or left? One option is to keep a count of the total descendants of each node, and always add to the child which has the fewest.

Another option is to keep count of the total number of nodes in the tree, and use the bits in that number (ignoring the first 1 bit) to decide on where to insert the new node. For example, if you have a tree with 5 nodes:

                 A
           B            C
         D   E

To add a new node, increment the node count to 6, which is 110 in binary. Ignore the first 1; interpret the next 1 as "go right" (which takes you to C) and the following 0 as "go left" (which tells you to insert as the left child of C). Your code becomes something like this:

void insert(char* titel, struct node **leaf, int nodeCount, int bitPos)
{
  if (*leaf == 0)
  {
    *leaf = (struct node*)malloc(sizeof(struct node));
    (*leaf)->titel = malloc(strlen(titel)+1);
    strcpy((*leaf)->titel,titel);
    (*leaf)->A = NULL;
    (*leaf)->B = NULL;
  }
  else
  {
     int currentBit = (nodeCount >> bitPos) & 1;
     if (currentBit == 0) {
       // insert to left
       insert(titel, &((*leaf)->A), nodeCount, bitPos - 1);
     }
     else
     {
       // insert to right
       insert(titel, &((*leaf)->B), nodeCount, bitPos - 1);
     }
  }
}

Notice I changed the return type to void since you don't need to return a value. I'll leave the calculation of the initial bitPos value as an exercise (remember: it's the position of the highest order 1 bit, minus 1).

If you also need to remove elements from the tree, you will need to find a way to re-balance it, however.

Note that there are several data structures and algorithms for maintaining balanced trees which support both insertion and deletion. See red-black trees and AVL trees for example. These are usually used for ordered trees, but it should be trivial to adapt them for an unordered-but-balanced tree.

edited Nov 29, 2017 at 1:48

answered Nov 29, 2017 at 0:42

davmac

20.8k1 gold badge45 silver badges72 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

David C. Rankin Over a year ago

Fairly reasonable links to both (with C code) are RedBlackTree - MIT and AVL Tree - ZenTut. (the Linux kernel also contains good implementations of both, but makes use of a significant number of macros)

Gerhard Haid Over a year ago

Thank you very kindly. But isn't there a way to create a height balanced binary tree without the requirement of me calculating the value of bitPos?

davmac Over a year ago

@GerhardHaid yes, as I already said: you can use an AVL tree or a Red-Black tree. But I don't see why calculating bitPos should be a problem (if you don't know how to do it, search, or ask a question if no suitable answer exists yet).

Gerhard Haid Over a year ago

Sir the tree you provided seems to be wrong. In my example I inserted 7 nodes and always the bitPos of the nodecount. The left side of the tree is correct, but the right side is wrong. It appears that instead of using root->B and then filling in A and B it creates only seperate B nodes.

davmac Over a year ago

@GerhardHaid pretty sure my code above is correct. Are you correctly incrementing the nodecount before inserting a new node? Without seeing your code I can't comment further. Maybe post it to ideone.com or similar and post a link here.

|

Collectives™ on Stack Overflow

How to add node to binary tree in C?

1 Answer 1

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related