Need help with tree-printing code

Question

I am trying to print this tree:

In this way:

1
2 3
4 5 6

I wrote this code:

void print_g(Tree t)
{
    Queue q=initQueue();
    Tree tmp=initTree();
    if(!isTreeEmpty(t))
        enqueue(q,t);
    while(!isQueueEmpty(q))
    {
        tmp=dequeue(q);
        printf("%d ",*((int *)Root(tmp)));
        if(!isTreeEmpty(subLeft(tmp)))
            enqueue(q,subLeft(tmp));
        if(!isTreeEmpty(subRight(tmp)))
            enqueue(q,subRight(tmp));

    }
}

But this code is printed like this:

123456

I can't think of an idea how to solve the print issue. Can someone write the Pseudo Code??

Thanks.

Your code doesn't have a "\n" anywhere, how do you expect it to display as you want? You must enque a separator at each level. — jman, Sep 08 '11 at 18:58
Dup of http://stackoverflow.com/questions/1104644/how-would-you-print-out-the-data-in-a-binary-tree-level-by-level-starting-at-th — jman, Sep 08 '11 at 18:59
Thats not really a duplicate question, this question is asking about how to add new lines to a BFS, not how to implement a BFS better. — Anthony, Sep 08 '11 at 19:14
For the purposes of helping to look things up, this kind of traversal is sometimes called *"iterative deepening"*. — dmckee --- ex-moderator kitten, Sep 08 '11 at 19:16

score 1 · Answer 1 · answered Sep 08 '11 at 18:57

1

After you add the children to the queue, create a fake tree node with the value being a newline character and add it to the queue.

answered Sep 08 '11 at 18:57

Anthony

906
1
8
19

1

Never mind, I thought you meant to print the newline character after adding the children to the queue. Enqueing it should work, although the OP would have to use some condition to fix the printf format. – Daniel Sep 08 '11 at 19:05

tdk001 · Answer 2 · 2011-09-08T19:24:48.427

You don't have any code to print a newline ('\n') after each generation of the tree.

You need to find some way to tell your program when a tree generation passes and then stick the '\n' in there.

Perhaps:

void print_g(Tree t)
{
    Queue q=initQueue();
    Tree tmp=initTree();
    if(!isTreeEmpty(t))
        enqueue(q,t);

    int dist = distanceFromTop(t); // new function to tell us which generation we are in

    while(!isQueueEmpty(q))
    {
        tmp=dequeue(q);

        if (distanceFromTop(tmp) != dist) // have we changed generation from previous iteration?
            printf("\n"); // if so, newline
        dist = distanceFromTop(tmp);

        printf("%d ",*((int *)Root(tmp)));
        if(!isTreeEmpty(subLeft(tmp)))
            enqueue(q,subLeft(tmp));
        if(!isTreeEmpty(subRight(tmp)))
            enqueue(q,subRight(tmp));

    }
}

Just be sure that your Tree definition has a member to hold its own distanceFromTop and fill this value in during initTree() to keep the algorithm from getting too slow.

How are you implementing the distanceFromTop() method? The best case I can think of would add O(n) time to the algorithm, but if you are planning on walking to the top of the tree once for each node than that is going to add O(n^2) time. — Anthony, Sep 08 '11 at 19:12
In my head, I'm implementing it as a simple lookup of a value stored during `Tree tmp=initTree();`. Any time a child node is added to a parent, that child is given its parent's distance +1, then goes down the tree to update its own children (likely not to be any given the sample data in the question) — tdk001, Sep 08 '11 at 19:20

Need help with tree-printing code

2 Answers2