would you please help me?
I wrote 3 separate line of code for printing my binary tree, and now I am trying to print the level-order traversal of the tree, where the nodes at each level of the tree are printed on a separate line.
my codes are below,( for printing inorder, preorder and post order)
I have no Idea how I can print them in , level-order traversal
I think I should use a Queue, but how? do you have any code that can help me?
would you please help me?
thanks. - template <typename T>
-
void Tree<T> :: printInOrder (std::ostream& out, TreeNode<T>* rootNode) {
-
if (rootNode != NULL) {
-
printInOrder (out, rootNode->left);
-
out << (rootNode->data) << " ";
-
printInOrder (out, rootNode->right);
-
}
-
return;
-
}
-
-
template <typename T>
-
void Tree<T> :: printPostOrder (std::ostream& out, TreeNode<T>* rootNode) {
-
if (rootNode != NULL) {
-
printPostOrder (out, rootNode->left);
-
printPostOrder (out, rootNode->right);
-
out << (rootNode->data) << " ";
-
}
-
return;
-
}
-
-
template <typename T>
-
void Tree<T> :: printPreOrder (std::ostream& out, TreeNode<T>* rootNode) {
-
if (rootNode != NULL) {
-
out << (rootNode->data) << " ";
-
printPreOrder (out, rootNode->left);
-
printPreOrder (out, rootNode->right);
-
}
-
return;
6 19988
You are right; you need to use a queue. Remember that a queue is a FIFO data structure - what you put in first must come out first. Keeping that in mind, when you traverse a tree, which nodes to you usually encounter first? The ones at the top, or the ones at the bottom?
Thanks
so, I came up with this code, but it dosent work,
would you please help me?
thanks - //level-order traversal
-
void Tree<T>::breadthFirst()
-
{
-
/* Temporary queue. */
-
Queue queue;
-
Tree<T> *traverse;
-
-
/*
-
* Gotta put something in the queue initially,
-
* so that we enter the body of the loop.
-
*/
-
queue.insert(root);
-
while (!queue.isEmpty()) {
-
traverse = queue.leave();
-
-
//Visit the node pointed to by traverse.
-
/*
-
* If there is a left child, add it
-
* for later processing.
-
*/
-
if (traverse->left!= NULL)
-
queue.insert(traverse->left);
-
/*
-
* If there is a right child, add it
-
* for later processing.
-
*/
-
if (traverse->right != NULL)
-
queue.insert(traverse->right);
-
}
-
-
}
I actually was able to write the code.
I am wondering how I can use the setw function in the iomanip library to print out appropriately spaced values so that the tree looks more "tree-like" rather than left-adjusted.
Would you please help me? - //level-order traversal
-
template<typename T>
-
void Tree<T> :: level_order_traversal(std::ostream& out, TreeNode<T>* rootNode)
-
{
-
/* Temporary queue. */
-
Queue <TreeNode<T>*> queue;
-
Tree<T> *traverse;
-
-
/*
-
* Gotta put something in the queue initially,
-
* so that we enter the body of the loop.
-
*/
-
int dep; //depth of the node
-
int temp=0;
-
queue.enter(root);
-
while (!queue.isEmpty()) {
-
rootNode = queue.leave();
-
if( depth(rootNode)!=temp){
-
temp=depth(rootNode);
-
out<<"\n";
-
}
-
-
out<<rootNode->data<<" ";
-
-
if (rootNode->left!= NULL)
-
queue.enter(rootNode->left);
-
-
if (rootNode->right != NULL){
-
queue.enter(rootNode->right);
-
}
-
}
-
-
-
}
Hmm...printing trees nicely is very tough. That's actually something I don't know how to do (that is, I don't have any solution fast at hand).
Maybe you can find out how many levels are in your tree (the height of the tree). Let's say the height is 5. So eventually you may have to print 2^(5-1) = 16 numbers in one line (the bottom line). Assuming 2 digit numbers, you want to use setw(3) to print the numbers. 3 spots * 16 numbers = 48 spaces. So your bottom line will take 2^(height-1) * (spaces_per_number) spaces (a.k.a. let:
max_size = pow(2, height-1) * spaces_per_number; )
Now, your root should be directly in the center of this value (it'll be at the center of the tree). So you move (max_size - spaces_per_number) / 2 spaces, print the root, then print a newline. Each time, you need to halve the amount you skip between numbers.
After this, it should just take a little experimentation to figure out where to print numbers, when to print extra spaces, etc. etc.
Thanks,
but I'm not able to write the code, I have no Idea how to make this work
would you please guid me more? or maybe you have a sample code,
thanks again
What is your depth function?
I think your depth function is not property working.
Sign in to post your reply or Sign up for a free account.
Similar topics
by: pembed2003 |
last post by:
Hi,
I have a question about how to walk a binary tree. Suppose that I have
this binary tree:
8
/ \
5 16
/ \ / \
3 7 9 22
/ \ / \ / \
|
by: Amit |
last post by:
Greetings All.
One of the usages that I need is accessing the contents of the container
that I am using in level order( which would mean breadth- first search
approach for a binary tree) as...
|
by: pembed2003 |
last post by:
Hi,
I have a question about how to walk a binary tree. Suppose that I have
this binary tree:
8
/ \
5 16
/ \ / \
3 7 9 22
/ \ / \ / \
|
by: GrispernMix |
last post by:
//ques and and level order traversal
file name: lab6_build_leaf_up.cpp
Instructions:
|
by: GrispernMix |
last post by:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <iostream>
#include <string.h>
using namespace std;
#define TRUE 1
#define FALSE 0
|
by: fdmfdmfdm |
last post by:
This might not be the best place to post this topic, but I assume most
of the experts in C shall know this.
This is an interview question. My answer is:
hash table gives you O(1) searching but...
|
by: phanipep |
last post by:
Construct the binary tree whose pre-order traversal is ABCDEFGH and Inorder traversal is CBDAFEGH, where each letter stands for the information stored in some node of the tree. show all the steps...
|
by: APEJMAN |
last post by:
would you please help me with this question?
I know that a binary tree can be recovered from its pre-order traversal. That is, a tree built from the pre-order traversal should always be the same as...
|
by: APEJMAN |
last post by:
hI
Would you please help me with this question?
Using Big O Notation, what is the running time of the level-order traversal ( the code below) in terms of the number of nodes N and the tree height...
|
by: Faith0G |
last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
|
by: ryjfgjl |
last post by:
In our work, we often need to import Excel data into databases (such as MySQL, SQL Server, Oracle) for data analysis and processing. Usually, we use database tools like Navicat or the Excel import...
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: aa123db |
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
| | |