Solved

Binary tree output to screen

Posted on 2007-11-29
7
1,075 Views
Last Modified: 2008-02-01
I'm trying to create a function that prints the binary tree out to the screen  making each column start 4 spaces to the right of the precious column.  Here is what I have so far.  I seem to have something out of order though.  Any thoughts ?


template <class ItemType>

void RTreeType<ItemType>::ScreenPrint (std::ostream& outFile, NodeType* tree, int spaces) const

{

if ( tree != NULL )

    {

        ScreenPrint(outFile,tree->right,spaces + 4);

        for ( int x=1; x <= spaces; ++x)

            cout << setw(4) << " ";

        cout << tree->info << endl;

        ScreenPrint(outFile,tree->left, spaces + 4);

    }

}

Open in new window

0
Comment
Question by:PMG76
7 Comments
 
LVL 40

Expert Comment

by:evilrix
ID: 20377587
It would help if you expanded a bit on what your actual problem is. Whilst it may very well be obvious to you it is not so obvious to others.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20377634
If I understand it correctly, you want to output the tree like this, correct ?

            1
        2       3
     4   5   6   7

If so, that's quite hard to do with a recursive function.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20377659
One approach would be to get the depth of the tree (to calculate the amount of spaces needed).

Then print one level of the tree at a time. The spaces at the beginning and between the values can be calculated based on the current level and the total depth of the tree.
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 

Author Comment

by:PMG76
ID: 20377672
yes that is what I need.  I'm aware of the difficulty, but I have to use recursion.  Right now my out put is like this:


    999
        500
            123
2

So something is not working properly
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 250 total points
ID: 20377736
>> I'm aware of the difficulty, but I have to use recursion.

Here's a way that is close to what I described earlier. Call the function recursively, rising in the tree starting from the lowest level, until you get to the root (highest level). Using the same calculation of amount of spaces, you can then print the current level. Something like :

        void printTree(TreeNode node, int level) {
            printTree(node->father, level + 1);
            // calculate amount of spaces based on current level (level starts counting from the bottom of the tree)
            // print the current level, using node->sibling to get the next sibling
        }

call by passing the leftmost node on the lowest level as the first parameter, and 0 as second parameter.
0
 
LVL 28

Expert Comment

by:pepr
ID: 20380428
If I understand the homework assingment well, one text line should display one node (tree rotated 90 degrees). If this is the case then the code is almost O.K. Only the for loop for generating the spaces can be simplified by using the variant of the std::string constructor that takes the counter and the character (remove the for loop completely.

By the way, your output can be fine if the root node contains 2, the right subtree has 999 in the top node, the left subtree is empty, etc.
cout << std::string(spaces, ' ') << tree->info << endl;

Open in new window

0
 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 250 total points
ID: 20383286
>>>> I'm aware of the difficulty, but I have to use recursion.

You could fill arrays instead of printing. And print the arrays with an outer function



template <class ItemType>
void RTreeType<ItemType>::ScreenPrint ()
{
      std::vector<std::vector<ItemType> > out;
      // now call the below recursive function with root node and level 0
      ...

      // here you need to iterate the arrays level by level and print
     
}
   
template <class ItemType>
void RTreeType<ItemType>::getValues(std::vector<std::vector<ItemType> >& out, NodeType* tree, int level) const
{
     if ( tree != NULL )
    {
        if ((int)out.size() <= level)
              out.push_back(std::vector<ItemType>());  // add a new vector if new level
        out[level].push_back(tree->info );
        ScreenPrint(out, tree->left,level+1);
        ScreenPrint(outFile,tree->right, level+1);
    }
}

That should bring you further but you still have to handle the spaces somehow. Maybe, by using a string instead of the inner vector<ItemType>. Then you have to insert spaces when an empty node occurs. And have to calculate offsets for each higher level.

You might consider to print the tree turned by 90 degrees:


       2

123
               500
      999

While the depth of a (somehow balanced) tree hardly was getting big, the width of a tree was growing exponentially.

Regards, Alex
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

861 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

24 Experts available now in Live!

Get 1:1 Help Now