#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2003
    Location
    Canada
    Posts
    228
    Rep Power
    12

    breadth-first traversal of a binary tree


    I have been looking at the breadth first traversal that DaWei included in his binary tree creation and display program. Here is just the showTree() function. I was actually on the verge of quitting trying because I feel over my head, and I am not looking for sympathy, just relating the reason for this post... since I have found this forum to be a great source of encouragement as well as help. Anyhooo, I understand that in all the references on the internet I can find to a breadth-first traversal, you need to make a FIFO structure, but don't understand why / how it is applied or works. If anyone is not too busy, could you give me a hand understanding. Just to cannibalize this code I need to understand more than I do.
    I am trying to write a basic breadth-first traversal that will print each level on a new line,
    Thanks...

    Code:
    void showTree (fP tQ, BTREE p, int l)
    {
        // Originally a much simpler breadth-first traversal, expanded
        // to graphically present the tree organization.
        int i = 0;
        int line, level = -1;
        char *sPos;
        BTREE trv;
        tQ->fUsage = 0;
        tQ->fSize = 64;
        tQ->fGet = tQ->fPut = &tQ->fData [0];
    
        put (tQ, p);
        while (tQ->fUsage)
        {
            trv = get (tQ);
            if (trv->level > level) level = trv->level;
            if (level > l) break;
            switch (level)
            {
            case 0: line = 0;
                break;
            case 1: line = 8;
                break;
            case 2: line = 12;
                break;
            case 3: line = 15;
                break;
            case 4: line = 17;
                break;
            }
            sPos = &screen [line][vCoord [i]];
            if (trv->d >= 0)
                sprintf (sPos, "%02d", trv->d);
            else
                sprintf (sPos, "%s", "  ");
            *(sPos + 2) = ' ';
            i++;
            if ((trv->left) || (trv->right))
            {
                if (trv->left)  put (tQ, trv->left);
                if (trv->right) put (tQ, trv->right);
            }
        }
        printf ("\n");
        for (i = 0; i < 18; i++) printf ("%s\n", screen [i]);
    }
    Last edited by gtpc; June 8th, 2004 at 02:36 PM.
  2. #2
  3. Lord of Dorkness
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2004
    Location
    Central New York. Texan via Arizona, out of his element!
    Posts
    8,524
    Rep Power
    3314
    Hi, Bob. Here's the code, stripped to traversal. I haven't compiled it since I stripped it, might have broken it . :o
    Code:
    void breadthFirst (fP tQ, BTREE p)
    {
        BTREE trv;
        tQ->fUsage = 0;
        tQ->fSize = 64;
        tQ->fGet = tQ->fPut = &tQ->fData [0];
    
        put (tQ, p);
        while (tQ->fUsage)
        {
            trv = get (tQ);
            printf ("%d ", trv->d);
            if ((trv->left) || (trv->right))
            {
                if (trv->left)  put (tQ, trv->left); 
                if (trv->right) put (tQ, trv->right);  
            }
        }
    }
    Here the while loop is 'unrolled' for clarity. It's a fifo, the 'get' works from top down. Simplified to neither child if no child, but
    as you can see with experimentation, it works either way.
    Code:
    put node (root)
    
    while nodes
    {
       get node, print it (root) (or otherwise record it)
       put left
       put right
    
       get node (left) print it (left)
       put left-left
       put left-right
    
       get node (right) print it (right)
       put right-left
       put right-right
    
       get node (left-left) print it NO CHILDREN, NO PUTS
       
       get node (left-right) print it NO CHILDREN, NO PUTS
    
       get node (right-left) print it NO CHILDREN, NO PUTS
    
       get node (right-right) print it NO CHILDREN, NO PUTS
    
       get node (fifo empty, break, done)
    }
    Regards,

    David

    EDIT: I see some hangover inefficiency there, part of the old show manipulation, trim away.

    EDIT 2: To print on a new line for each level, you'll need to add level information back in or derive it. It easily prints a breadth first traversal a level per line regardless of tree completeness, however, it won't print a proper positional representation of an incomplete tree without faking a complete tree with padding. Thus all the hooraw in the showTree procedure, as well as the padTree thangy. Cute, though, if I say so mesel' :cool: .
    Last edited by DaWei_M; June 4th, 2004 at 04:25 PM.
    Functionality rules and clarity matters; if you can work a little elegance in there, you're stylin'.
    If you can't spell "u", "ur", and "ne1", why would I hire you? 300 baud modem? Forget I mentioned it.
    DaWei on Pointers Politically Incorrect.
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2003
    Location
    Canada
    Posts
    228
    Rep Power
    12
    Thanks Dave. I will have a look at this and see if I can make it work. I really want to get past this AND understand it.

    EDIT: you are right, I need to get some level info in this. That is in fact one of the great hurdles here. I see even in your code that you added 'int level' in the struct node, but I don't see anywhere in the program where level is added to. Since the level goes basically :
    level 1, 1 node
    level 2, 2 nodes
    level 3, 4, nodes, etc, I see it is times 2 each level, I am thinking is there a way I can just use that? Of course then when I move on to general trees, which are not binary (do not have 2 children per parent) it will be useless... sigh****
    Last edited by gtpc; June 4th, 2004 at 05:18 PM.
  6. #4
  7. Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Apr 2004
    Location
    Frostbite capital of the world
    Posts
    542
    Rep Power
    11
    [QUOTE=gtpc] you need to make a FIFO structure, but don't understand why / how it is applied or works. [/QOUTE]


    say this is your tree
    Code:
                h
             /       \
            d         p
          /  \        / \
        b    f       k   s
        /\   /\     /\   /\
       a c  e g   j m r   t
    You start at the top node(h), you do what you have to and then you add the two children to the FIFO
    FIFO = d->p
    You visit d (remove from FIFO) and add it's children to the FIFO
    FIFO=p->b->f
    Now you visit p(remove from FIFO) and add it's children
    FIFO=b->f->k->s
    Now you visit b(remove from FIFO) and add it's children.
    FIF0=f->k->s->a->c
    etc until your FIFO is empty(NULL)


    If you don't need to keep track of what level the node appears in the tree it's just a matter of having a simple link list with a top and an end pointer. You add the pointers(to tree node) of the children to the end pointer, and you remove the pointers(to tree nodes) from the top pointer.

    By doing you get a list of all the pointers to the nodes in the same level in the tree in a row in FIFO. All the pointers to the nodes directly below that level, will follow those pointers.

    If you have to keep track of what level each node(tree) appears in the tree you'll have to add a int level to each node of the FIFO. Of course the children of a node, will be one level further down the tree than the parent.

    If you're trying to print out a "image" of the tree, and it's not a complete tree, you'll have to add another int variable call it x to each node of the FIFO, that keeps track of how far to the right the node appears in a tree. The left child will have that value 2*x-1, and the right child will have that value 2*x. In this way you can calculate how many nodes are missing between two nodes that appear in that level of the tree.
    Last edited by fisch; June 4th, 2004 at 07:13 PM.
  8. #5
  9. Lord of Dorkness
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2004
    Location
    Central New York. Texan via Arizona, out of his element!
    Posts
    8,524
    Rep Power
    3314
    The count levels procedure. Pretty sure it would work for ternary and greater trees with suitable additions.
    Code:
    int countLevels (BTREE p, int level)
    {
        // This is simpler if you only record the level in
        // the node and don't return it.
        // If you return it, the greater of the l (lesser or left) and g (greater/right)
        // levels is returned from each recursive call
        int lLevel = 0, gLevel = 0; // Not necessary unless the level count is to be returned
        p->level = level;           // Puts the level in the node
        level++;                    // Increments the level to pass to the children
        // Pass their level to the children in the recursive call
        if (p->left) lLevel = countLevels (p->left, level);
        if (p->right) gLevel = countLevels (p->right, level);
        // Test for the greatest level from the two children and return it.
        gLevel = gLevel > lLevel? gLevel : lLevel;
        level = level > gLevel? level : gLevel;
        return level;
    }
    Functionality rules and clarity matters; if you can work a little elegance in there, you're stylin'.
    If you can't spell "u", "ur", and "ne1", why would I hire you? 300 baud modem? Forget I mentioned it.
    DaWei on Pointers Politically Incorrect.
  10. #6
  11. Lord of Dorkness
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2004
    Location
    Central New York. Texan via Arizona, out of his element!
    Posts
    8,524
    Rep Power
    3314
    Fisch is correct that the proper position on the screen can be calculated if the nodes are labeled. The tree can be displayed without requiring gotoxy type positioning and just constructed with the proper number of spaces. I did it this way once.

    Unfortunately, the 'tween' spacing for each line varies and it really gets hairy if you want to take advantage of overlapping into empty areas where possible to reduce the tree width. It turns out to be simpler to just make a 2D template of spaces and connectors and plop the values into the appropriate position in the grid. The five-level limit I have is based on a good fit to an 80-char line.

    That confusing array, vCoord, is just a sequential list of all the horizontal positions, without regard to line number. You'll notice in showTree that the index begins at 0 and just goes up one for each thangy printed, whether it's node contents or spaces for a dummy node, no attention paid to level by 'i', just incremented through the position list.
    Functionality rules and clarity matters; if you can work a little elegance in there, you're stylin'.
    If you can't spell "u", "ur", and "ne1", why would I hire you? 300 baud modem? Forget I mentioned it.
    DaWei on Pointers Politically Incorrect.
  12. #7
  13. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2003
    Location
    Canada
    Posts
    228
    Rep Power
    12
    Hahaha! This is worse than I thought. And the sun and warmth and my bike and the golf course are not helping! Dave, are you saying that the countLevels() function is where I get my level info to insert in each node. I dont want to make a 2D tree, but in order to print a newline for each level, don't I still need level info in each node?
  14. #8
  15. Lord of Dorkness
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2004
    Location
    Central New York. Texan via Arizona, out of his element!
    Posts
    8,524
    Rep Power
    3314
    You need the level info. countLevels is putting it into each node with this statement:
    Code:
        p->level = level;           // Puts the level in the node
    You start with zero, that gets put into the root node. You bump it one and do a recursive call to the children. They bump it one and call THEIR children. Child subtrees may not each be the same depth, so when both children return, you take the deepest level and return that to YOUR caller, so the final answer returned to main is the deepest level. However, that has no bearing on the level stashed in the nodes, which goes up one for each set of children called.

    Then, when you do the breadth-first, you start with a reference level value of zero and start printing the nodes. When a node's level value goes above the reference level, you generate a newline and set the reference level to the new level. Then, when a node's level goes above THAT, you generate another newline, and so on.

    Sunny and warm here too, but my 2-wood looks suspiciously like a weed eater :-).

    Regards.
    Functionality rules and clarity matters; if you can work a little elegance in there, you're stylin'.
    If you can't spell "u", "ur", and "ne1", why would I hire you? 300 baud modem? Forget I mentioned it.
    DaWei on Pointers Politically Incorrect.
  16. #9
  17. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2003
    Location
    Canada
    Posts
    228
    Rep Power
    12
    Hey there again. Instead of using countLevels(), I just included a level++ in create_tree() and as you can see by running the program, it puts the correct levels on each node (perhaps it would not on an incomplete tree. Regardless, I am still having trouble to output a newline at the end of each new level. It was of course simple for the root, again as you can see in the breadthFirst function, but beyond that, where do I go? Thought I was on a roll since I have the level information in each node now. Suggestions? Help?

    Code:
    /* question 10_34, print out the nodes of a binary tree in level 
    order. The root node is at level 0. On the next level of nodes are the
    children of the previous level. First, print the root node. Then print 
    the left child and the right child that are at level 1. Continue printing 
    the nodes from left to right, level by level. This is called breadth-first 
    traversal */
    
    
    #include <assert.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    #define SIZE 15
    
    typedef  int  DATA;
    
    struct node {
       DATA		d;
       struct node	*left;
       struct node	*right;
       int		level;
    };
    
    typedef struct node NODE;
    typedef NODE	    *BTREE;
    
    // Simple fifo definition, used to institute
    // a breadth-first traversal.
    typedef struct sFifo *fP;
    typedef struct sFifo
    {
        BTREE  fData [64];
        int fSize;
        int fUsage;
        BTREE  *fPut;
        BTREE  *fGet;
    } cFifo;
    
    void inorder(const BTREE root);
    void preorder(const BTREE root);
    void postorder(const BTREE root);
    BTREE new_node();
    BTREE init_node(DATA d1, BTREE p1, BTREE p2, int level);
    BTREE insert(BTREE parent, BTREE root, int item);
    int  count_nodes(BTREE root, int cnt);
    int  count_Lnodes(BTREE root, int cnt);
    BTREE create_tree(int a[], int i, int size, int level);
    int *order_array(int a[]);
    void divide_array(int a[], int b[], int c[], int size);
    int find_center(int a[], int size);
    void print_array(int ordered_array[]);
    void bfTraversal(BTREE parent, BTREE root, int i, int j);
    void breadthFirst (fP tQ, BTREE p);
    BTREE get (fP q);
    void put (fP q, BTREE p);
    int countLevels (BTREE p, int level);
    
    int main(void)
    {
       BTREE b_tree;
       int array_of_ints[] = {2, 4, 6, 7, 8, 9, 11, 12, 15, 17, 21, 23, 24, 27, 30};
       int key[15] = {0};
       int *keyPtr = 0;
       int nLevels;
       cFifo  treeQ = {0};
    
       b_tree = create_tree(array_of_ints, 0, SIZE, 0);
       printf("Tree printed 'pre-order'\n");
       preorder (b_tree);
       printf("\nTree inorder\n");
       inorder (b_tree);
       putchar('\n');
       printf("Number of nodes = %d\n", count_nodes(b_tree, 0));
       printf("Number of Leaf nodes = %d\n", count_Lnodes(b_tree, 0));
       printf("The tree in breadth-first order...\n");
       breadthFirst(&treeQ, b_tree);
       putchar('\n');
       return 0;
    }
    
    /* breadth-first traversal for a binary tree */
    void breadthFirst (fP tQ, BTREE p)
    {
        BTREE trv;
        tQ->fUsage = 0;
        tQ->fSize = 64;
        tQ->fGet = tQ->fPut = &tQ->fData [0];
    
        put (tQ, p);
        while (tQ->fUsage)
        {
            trv = get (tQ);
    	{
               printf ("%d ", trv->d);
               if ((trv->left) || (trv->right))
               {
                   if (trv->left) put (tQ, trv->left);
                   if (trv->right) put (tQ, trv->right);
               }
               if (trv->level == 1) putchar('\n'); // new line after EACH line is full??
    	}
        }
    }
    
    /* inorder binary tree traversal and print */
    void inorder(const BTREE parent)
    {
       if (parent != NULL) {
          inorder(parent->left);  /* recur left */
          printf("%d ", parent->d);
          inorder(parent->right); /* recur right */
       }
    }
    
    /* preorder binary tree traversal and print */
    void preorder(const BTREE root)
    {
       if (root != NULL) {
          printf("%d (level->%d), \n", root->d, root->level);
          preorder(root->left);  /* recur left */
          preorder(root->right); /* recur right */
       }
    }
    
    /* creating binary trees */
    BTREE new_node()
    {
       return (malloc(sizeof(NODE)));
    }
    
    BTREE init_node(DATA d1, BTREE p1, BTREE p2, int level)
    {
       BTREE t;
       t = new_node();
       t->d = d1;
       t->left = p1;
       t->right = p2;
       t->level = level;
       return t;
    }
    
    // create ordered binary tree using recursion, divide array, then insert center int
    BTREE create_tree(int a[], int i, int size, int level)
    {
       int b[SIZE] = {0}, c[SIZE] = {0};
    
       if (size == 0) return NULL;
       if (size == 1) init_node(a[0], NULL, NULL, level);
       if (i <= SIZE)
       {
          level++;
          divide_array(a, b, c, size);    // b and c are a divided in 2
          return init_node(find_center(a, size), create_tree(b, 2*i+1, size-size/2-1, level),
                                                 create_tree(c, 2*i+2, size/2, level), level);
       }
    }
    
    void print_array(int ordered_array[])
    {
       int i;
    
       for (i = 0; i < SIZE; ++i)
          printf("%d ", ordered_array[i]);
       putchar('\n');
       putchar('\n');
    }
    
    // put an array in alphabetical order
    int *order_array(int a[])
    {
       int j, i, temp;
       int *b = a;
    
       for (i = 0; i < SIZE-1; ++i)
          for (j = i+1; j < SIZE; ++j)
             if (a[i] > a[j])
    	 {
                temp = a[i];
                a[i] = a[j];
    	    a[j] = temp;
    	 }
       return b;
    }
    
    // send function a, the array to be divided, and b and c, the 2 array pointers
    void divide_array(int a[], int b[], int c[], int size)
    {
       int i, j;
    
       for (i = 0; i < size/2; ++i) b[i] = a[i];
          i++;  // removing middle item, the one being added
       for (j = 0; i < size; ++i, ++j) c[j] = a[i];
    }
    
    // find center of an array
    int find_center(int a[], int size)
    {
       int center;
    
       center = (size-1)/2;
       return a[center];
    }
    
    // count total number of nodes
    int  count_nodes(BTREE root, int cnt)
    {
       if (root != NULL) {
          cnt = count_nodes(root->left, cnt);  /* recur left */
          cnt = count_nodes(root->right, ++cnt); /* recur right */
       }
       return cnt;
    }
    
    // count number of leaf nodes
    int count_Lnodes(BTREE root, int cnt)
    {
       if (root != NULL) {
          cnt = count_Lnodes(root->left, cnt);
          cnt = count_Lnodes(root->right, cnt);
          if (root->left == NULL && root->right == NULL) ++cnt;
       }
       return cnt;
    }
    
    BTREE get (fP q)
    {
        // Simple fifo get procedure
        BTREE p = NULL;
        if (q->fUsage)
        {
            q->fUsage--;
            p = *q->fGet++;
        }
        return p;
    }
    
    void put (fP q, BTREE p)
    {
        // Simple fifo put procedure
        if (q->fUsage < q->fSize)
        {
            *q->fPut++ = p;
            q->fUsage++;
        }
    }
    
    // not used in this program right now
    int countLevels (BTREE p, int level)
    {
        // This is simpler if you only record the level in
        // the node and don't return it
        int lLevel = 0, gLevel = 0;
        p->level = level;
        level++;
        if (p->left) lLevel = countLevels (p->left, level);
        if (p->right) gLevel = countLevels (p->right, level);
        gLevel = gLevel > lLevel? gLevel : lLevel;
        level = level > gLevel? level : gLevel;
        return level;
    }
    Last edited by gtpc; June 8th, 2004 at 02:34 PM.
  18. #10
  19. Lord of Dorkness
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2004
    Location
    Central New York. Texan via Arizona, out of his element!
    Posts
    8,524
    Rep Power
    3314
    Nothing wrong with putting the level in the node when you generate the tree, if the tree doesn't change. I did it as I did because of tree rearrangements caused by insertions, deletions, re-heaping, and so forth. I'll have a look. Meanwhile, you hit a bucket of balls for me and I'll have a six-pack for you :-).
    Functionality rules and clarity matters; if you can work a little elegance in there, you're stylin'.
    If you can't spell "u", "ur", and "ne1", why would I hire you? 300 baud modem? Forget I mentioned it.
    DaWei on Pointers Politically Incorrect.
  20. #11
  21. Lord of Dorkness
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2004
    Location
    Central New York. Texan via Arizona, out of his element!
    Posts
    8,524
    Rep Power
    3314
    Procedure modified and commented.
    Code:
    /* breadth-first traversal for a binary tree */
    void breadthFirst (fP tQ, BTREE p)
    {
        int level; // Keep track of CURRENT level
        BTREE trv;
        tQ->fUsage = 0;
        tQ->fSize = 64;
        tQ->fGet = tQ->fPut = &tQ->fData [0];
    
        // We want every level to begin with a new line, so 
        // set this value to trigger a new line for even the root.
        level = -1;
    
        put (tQ, p);
        while (tQ->fUsage)
        {
            trv = get (tQ);
        	{
               // Check to see if the level has changed
               if (trv->level > level)
               {
                   // It has changed, print a new line
                   printf ("\n");
                   // Store the new level for subsequent comparisons
                   level = trv->level;
               }
               // Print the node value; happens regardless of level change
               printf ("%d ", trv->d);
               // I took out the redundant test for node validity here
               if (trv->left) put (tQ, trv->left);
               if (trv->right) put (tQ, trv->right);
    	    }
        }
    }
    Output:
    Code:
    Tree printed 'pre-order'
    12 (level->1),
    7 (level->2),
    4 (level->3),
    2 (level->4),
    6 (level->4),
    9 (level->3),
    8 (level->4),
    11 (level->4),
    23 (level->2),
    17 (level->3),
    15 (level->4),
    21 (level->4),
    27 (level->3),
    24 (level->4),
    30 (level->4),
    
    Tree inorder
    2 4 6 7 8 9 11 12 15 17 21 23 24 27 30
    Number of nodes = 15
    Number of Leaf nodes = 8
    The tree in breadth-first order...
    
    12
    7 23
    4 9 17 27
    2 6 8 11 15 21 24 30
    Press any key to continue
    Functionality rules and clarity matters; if you can work a little elegance in there, you're stylin'.
    If you can't spell "u", "ur", and "ne1", why would I hire you? 300 baud modem? Forget I mentioned it.
    DaWei on Pointers Politically Incorrect.
  22. #12
  23. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2003
    Location
    Canada
    Posts
    228
    Rep Power
    12
    OF course, put the newline at the beginning, etc.! I must broaden my mind, and thanks a bunch. That is exactly what I was trying to get.
  24. #13
  25. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2013
    Posts
    1
    Rep Power
    0

    Full Code


    Hello, im a beginning on c and i need this Breadth First full code can we send it to me?

    When i copy all codes above it say just one thing that i really dont know how to repair.

    1 IntelliSense: return value type does not match the function type c:\Users\wilme\Documents\Visual Studio 2012\Projects\ConsoleApplication4\ConsoleApplication4\ConsoleApplication4.cpp 120 11 ConsoleApplication4

    can we help me solve it?

    follow the location of error in the code.

    BTREE new_node()
    {
    return (malloc(sizeof(NODE)));
    }

IMN logo majestic logo threadwatch logo seochat tools logo