Thread: Create a balanced (not BST) tree

You probably will find some value in reading through Prelude's Tutorials on data structures. They are pretty comprehensive and easy to follow.

Before creating a new level in the tree, all the nodes of the current level must be filled.

So you want a perfect tree.

I've been trying to do it, but it seems more complex than i tought.

Not especially. Look into level order searches and incorporate that process into your insertion procedure. In the absence of any ordering method, making a perfect tree is indeed harder if you use a depth first search for finding the next insertion point while a level order search makes it almost trivial.

You are describing filling a tree breadth-first. That is actually quite easy. The trick is to look at the count of the number of nodes that will be in the tree, in binary.

Then look at the bits from the second leftmost bit set (ignoring the first 1 in other words) to the rightmost bit. If the bit is a zero go left, and if it is a one go right.


So say you had 5 nodes currently in the tree and you want to insert the sixth one. What you have:

Code:

      A
    /   \
   B     C
  / \
 D   E

First take the nunber of nodes plus 1 in binary. It's 5+1 = 6 which is 110 in binary. So ignoring the leftmost 1 gives us 10. That means go right, then left, and then insert there:

Code:

      A
    /   \
   B     C
  / \   /
 D   E F

Now if you want to insert another, the current tree count is 6 and 6+1 = 7 which is 111 in binary, so dropping the leading 1 you get 11 and go right twice:

Code:

      A
    /   \
   B     C
  / \   / \
 D   E F   G

Next insert there are 7 nodes already. 7+1 = 8 and that's 1000 in binary.
Skip the leading one and you get 000 which means go left three times and as you can see that cleary places the node on the start of the next level down.


Edit:
The other easy and more efficient way is to put a pointer to each node you insert onto the back of a queue. You repeatedly pop the first node from the queue, attach a left and right child onto it and then put the left and right child onto the back of the queue. When you've filled the tree with enough nodes, just throw away your queue and you're done.

Second edit: Oh and that'll be the "Level Order Search" Prelude referred to.

Originally Posted by kr0n1x

I found a way to implement it with a queue.

I should make the code better (at least the level_insert() function), but I'll post it anyway just for someone who could need it.

Tree level insert with a queue: [C] level_insert - Pastebin.com

Thanks for posting your solution; let's just move that into the page so we don't loose that link in the future.

Code:

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

/* this is going to contain the queue, made of pointers to tree's nodes */
struct queue {
    struct node *pointer;
    struct queue *next;
};

/* this represents the tree's nodes */
struct node {
    int inf;
    struct node *left;
    struct node *right;
};

void level_insert(struct node **); // enter a new node into the tree keeping it a "complete tree"
void inQueue(struct queue **, struct queue **, struct node *); // push a node into the queue
struct node *outQueue(struct queue **, struct queue **); // pop a node out of the queue
void preorder(struct node *); // tree's preorder visit (just for test purpose)
void level_visit(struct node *); // tree's level visit

int main(void) {
    struct node *Tree = NULL;
    int i;

    /* I'm making the tree this way to be sure it's made how I want xD */
    Tree = (struct node *)malloc(sizeof(struct node));
    Tree->inf = 5;

    Tree->left = (struct node *)malloc(sizeof(struct node));
    Tree->left->inf = 3;

    Tree->right = (struct node *)malloc(sizeof(struct node));
    Tree->right->inf = 7;
    Tree->left->left = (struct node *)malloc(sizeof(struct node));
    Tree->left->left->inf = 10;
    Tree->left->left->left = NULL;
    Tree->left->left->right = NULL;
    Tree->left->right = (struct node *)malloc(sizeof(struct node));
    Tree->left->right->inf = 8;
    Tree->left->right->left = NULL;
    Tree->left->right->right = NULL;
    Tree->right->left = (struct node *)malloc(sizeof(struct node));
    Tree->right->left->inf = 4;
    Tree->right->left->left = NULL;
    Tree->right->left->right = NULL;
    Tree->right->right = NULL;

    /* preorder visit to be sure the tree is made correctly */
    preorder(Tree);

    printf("\n\n");

    level_insert(&Tree); // entering a new node

    level_visit(Tree); // showing the new tree

    level_insert(&Tree); // entering another new node

    level_visit(Tree); // level visit test again :D

    for(i = 0; i < 10; ++i) {
        level_insert(&Tree);
        level_visit(Tree);
    }

    return 0;
}

void level_visit(struct node *a) {
    struct queue *testa = NULL, *coda = NULL;
    struct node *aus = a;

    if(a != NULL) {
        inQueue(&testa, &coda, aus);
        while(testa != NULL) {
            aus = outQueue(&testa, &coda);
            printf("%d ", aus->inf);
            if(aus->left != NULL)
                inQueue(&testa, &coda, aus->left);
            if(aus->right != NULL)
                inQueue(&testa, &coda, aus->right);
        }
    }
}

void level_insert(struct node **a) {
    struct queue *testa = NULL, *coda = NULL;
    struct node *aus = *a;
    int flag = 0;

    if(*a != NULL) {
        inQueue(&testa, &coda, aus);
        while(testa != NULL && flag == 0) {
            aus = outQueue(&testa, &coda);
            if(aus != NULL) {
                if(aus->left == NULL || aus->right == NULL) {
                    if(aus->left == NULL) {
                        aus->left = (struct node *)malloc(sizeof(struct node));
                        printf("\nEnter a number: ");
                        scanf("%d", &(aus->left->inf));
                        aus->left->left = NULL;
                        aus->left->right = NULL;
                        flag = 1;
                    }
                    else {
                        aus->right = (struct node *)malloc(sizeof(struct node));
                        printf("\nEnter a number: ");
                        scanf("%d", &(aus->right->inf));
                        aus->right->left = NULL;
                        aus->right->right = NULL;
                        flag = 1;
                    }

                }
                else {
                    inQueue(&testa, &coda, aus->left);
                    inQueue(&testa, &coda, aus->right);
                }
            }
            else {
                aus = (struct node *)malloc(sizeof(struct node));
                printf("\nEnter a number: ");
                scanf("%d", &(aus->inf));
                aus->left = NULL;
                aus->right = NULL;
                flag = 1;
            }
        }
    }
    else {
        *a = (struct node *)malloc(sizeof(struct node));
        printf("\nEnter a number: ");
        scanf("%d", &((*a)->inf));
        (*a)->left = NULL;
        (*a)->right = NULL;
    }
}

void inQueue(struct queue **head, struct queue **tail, struct node *ele) {
    struct queue *nuovo = NULL;

    nuovo = (struct queue *)malloc(sizeof(struct queue));
    nuovo->pointer = ele;
    nuovo->next = NULL;


    if(*tail != NULL)
        (*tail)->next = nuovo;

    else
        *head = nuovo;

    *tail = nuovo;

}

struct node *outQueue(struct queue **head, struct queue **tail) {
    struct node *aus = NULL;

    aus = (*head)->pointer;

    if(*head != NULL) {
        *head = (*head)->next;
        if(*head == NULL)
            *tail = NULL;
    }

    return aus;
}

void preorder(struct node *p) {
    if(p != NULL) {
        printf("%d ", p->inf);
        preorder(p->left);
        preorder(p->right);
    }
}

You could simplify your tree enqueue and dequeue routines somewhat by making the assumtion that the queue never becomes empty. Then you can ensure that this remains true by placing the first node in the queue explicitly, only peeking at the top node each time, and putting the children on the back prior to doing a pop-front.
Each operation is then very short:

Code:

//enqueue:
tail->next = newNode;
tail = newNode;

//peek:
return head;

//dequeue:
temp = head;
head = head->next;
free(temp);

When peeking at the top node you should never encounter a NULL because you would never put a NULL into the queue.

level_insert is also way more complicated than it needs to be. Every node that reaches the head of the queue and gets peeked at will have no children at that point. Without even examining them you can just immediately create both new children and assign these to the left and right pointers, nulling the grandchild pointers of course. Something like the following pseudocode:

Code:

add first item to head of tree
while more items to add
   create left child
   assign new child to peek()->left
   put left child onto queue tail
   if more items to add
      create right child
      assign new child to peek()->right
      put right child onto queue tail
   pop from the head of the queue
destroy queue

This will just build your whole tree for you and would be suited to building the tree as it is read in from file for example.