CODEWITHSUNDEEP
cdata-structurestree
user1386966
user1386966

Reputation: 3392

How to print level order tree (not binary) in C?

I was looking at the question being asked here, but found only answers regarding binary trees. I want to print in level order a tree that has 0 - n children. I know the number of children, but my code isn't working

The algorithm I thought is:

but the problem is that I don't know where to stop, and when I try recursively, I fail.

This is the function that I wrote:

void printBFS(myStruct s)
   {
      int i = 0;
      printAllChildrenData(s);
      for (i = 0; i < s->number_of_children; i++)
        {
            myStruct childCurr = getChildAtIndex(s, i);
            printBFS(chilCurr);
        }
   }

I'm messing here something. I hope the functions are clear: the printAllChildrenData prints all the data of all the children of S; it goes over the children list and prints it.

Editing If I have this tree for example:

           1
     2        7        8
  3    6            9     12
 4 5              10 11

it should print:

1 2 7 8 3 6 4 5 9 12 10 11

instead of:

1 2 7 8 3 6 9 12 4 5 10 11

Upvotes: 1

Views: 2536

Answers (3)

Jonathan Leffler
Jonathan Leffler

Reputation: 753555

This code, which is closely based on your code (but expanded into a SSCCE), produces the output:

 1 2 7 8 3 6 4 5 9 12 10 11

The code uses the designated initializer feature of C99 (one of the most useful additions to C99, IMNSHO). I've chosen to use a 'better' name than myStruct for the structure; it represents a tree, so that's what it is called. I've also not hidden the pointer in the typedef, and made the printing code const-correct (printing code should not normally modify the data structure it is operating on). It also uses the C99 option to declare a variable in the first clause of a for loop. I introduced an extra function, printTree(), which prints the data from the root node, calls your printBFS() to print the body of the tree, and prints a newline to mark the end of the output; the printTree() function is called to print a tree. Note the systematic use of printData() to print the data for a node. If the data was more complex than a single integer, this would allow you to write the printing code once.

Careful study of the code will show that the printBFS() below is isomorphic with what you show, which in turn suggests that your problem is not in the code you show. That means it is probably in the code you use to build the tree, rather than in the code used to print it. Since you've not shown us the tree-building code, it makes it hard for us to predict what the problem is.

#include <stdio.h>
#include <assert.h>

enum { MAX_CHILDREN = 3 };
typedef struct Tree Tree;

struct Tree
{
    int data;
    int number_of_children;
    Tree *children[MAX_CHILDREN];
};

static void printData(const Tree *s)
{
    printf(" %d", s->data);
}

static void printAllChildrenData(const Tree *s)
{
    for (int i = 0; i < s->number_of_children; i++)
        printData(s->children[i]);
}

static const Tree *getChildAtIndex(const Tree *s, int i)
{
    assert(s != 0 && i >= 0 && i < s->number_of_children);
    return(s->children[i]);
}

static void printBFS(const Tree *s)
{
    printAllChildrenData(s);
    for (int i = 0; i < s->number_of_children; i++)
    {
        const Tree *childCurr = getChildAtIndex(s, i);
        printBFS(childCurr);
    }
}

static void printTree(const Tree *s)
{
    printData(s);
    printBFS(s);
    putchar('\n');
}

/*
**             1
**       2        7        8
**    3    6            9     12
**   4 5              10 11
*/

static Tree nodes[] =
{
    [ 1] = {  1, 3, { &nodes[ 2], &nodes[ 7], &nodes[ 8] } },
    [ 2] = {  2, 2, { &nodes[ 3], &nodes[ 6], 0          } },
    [ 3] = {  3, 2, { &nodes[ 4], &nodes[ 5], 0          } },
    [ 4] = {  4, 0, { 0,          0,          0          } },
    [ 5] = {  5, 0, { 0,          0,          0          } },
    [ 6] = {  6, 0, { 0,          0,          0          } },
    [ 7] = {  7, 0, { 0,          0,          0          } },
    [ 8] = {  8, 2, { &nodes[ 9], &nodes[12], 0          } },
    [ 9] = {  9, 2, { &nodes[10], &nodes[11], 0          } },
    [10] = { 10, 0, { 0,          0,          0          } },
    [11] = { 11, 0, { 0,          0,          0          } },
    [12] = { 12, 0, { 0,          0,          0          } },
};

int main(void)
{
    printTree(&nodes[1]);
    return(0);
}

You can easily revise the testing to print each node in turn:

enum { NUM_NODES = sizeof(nodes) / sizeof(nodes[0]) } ;

int main(void)
{
    for (int i = 1; i < NUM_NODES; i++)
        printTree(&nodes[i]);
    return(0);
}

Upvotes: 1

David
David

Reputation: 1419

You could have a function like printElementsAtLevelN(int n) that traverses the tree, keeping track of how deep it is, and only prints elements at the right level. If you have it return the number of elements printed, you could have a loop that does something like:

while (printElementsAtLevelN( n ))
{
    n++;
}

The disadvantage to this is that you traverse parts of the tree many times, but if the tree isn't huge, that might not be an issue.

Upvotes: 1

jxh
jxh

Reputation: 70382

You need a list structure (or some other container). The pseudo code would be along the lines of:

ListOfNodes list
ListOfNodes children
add_node(list, root)
repeat {
    while (list not empty) {
        print top_node(list)
        add_children(children, top_node)
        pop_top(list)
    }
    list = children
    clear_all(children)
} until (list is empty)

Upvotes: 0

Related Questions