I have an algorithm question and don't know how to do it nicely.
Write a function to print nodes of binary tree, for each leaf node, print nodes from root node to leaf node.
For example, the following binary tree has 4 leaf nodes.
30
25 36
39 40 10 64
The resulting of print should be :
30, 25, 39
30, 25, 40
30, 36, 10
30, 36, 64 3 1656
Are the nodes supposed to be sorted? Or what order do you need them printed?
Usually going through a tree is a recursive procedure, and a node is only
accessed (i.e. printed) once. Why do you keep printing 30? A node that is a
leaf to the level above is a root to the level below. Here is a simple
algorithm.
curr = head;
printFunc( curr);
printFunc( root)
{
if root.left
printFunc(root. left);
print root;
if root.right
printFunc(root. right);
}
I think your tree would print as follows (I didn't code this, just a quick
run through in my head).
39 25 40 30 10 36 64
HTH,
kevin aubuchon
"Tracey" <Tr****@discuss ions.microsoft. com> wrote in message
news:94******** *************** ***********@mic rosoft.com... I have an algorithm question and don't know how to do it nicely. Write a function to print nodes of binary tree, for each leaf node, print
nodes from root node to leaf node. For example, the following binary tree has 4 leaf nodes. 30 25 36 39 40 10 64
The resulting of print should be : 30, 25, 39 30, 25, 40 30, 36, 10 30, 36, 64
Tracey wrote: I have an algorithm question and don't know how to do it nicely. Write a function to print nodes of binary tree, for each leaf node, print
nodes from root node to leaf node. For example, the following binary tree has 4 leaf nodes. 30 25 36 39 40 10 64
The resulting of print should be : 30, 25, 39 30, 25, 40 30, 36, 10 30, 36, 64
printTree (tree, new Stack ());
void printTree (Tree root, Stack path)
{
// Are we at a leaf?
if ((root.left == null) && (root.right == null))
{
// It's a leaf, print the path and the leaf
print (path);
print (root);
}
else
{
// Not a leaf, so remember this node as part of the path and keep
going...
nodes.push (root);
// Stop at the light, look both ways, look both ways again...
if (root.left != null)
{
printTree (root.left, path);
}
if (root.right != null)
{
printTree (root.right, path);
}
// Well, we're done with this node, it's no longer prt of the path
node.pop ();
}
}
Off the top of my head, untested etc. Hope this helps.
Hilton
Briefly, you'd do this with a recursive depth-first traversal of the tree.
For each child of the root, pass an argument to the traversal routine that
would be a string containing the node number of the root. Each child would
add a comma and a space and its own node number, and recursively pass that
along to its child nodes, unless it had no children (i.e., was a leaf node),
in which case it would print out the string.
Thus, in the example given, the root node would pass "30" to its direct
children, nodes 25 and 36 would pass (respectively) "30, 25" and "30, 36" to
each of their children, and each of the leaf nodes would add their own node
numbers to the string they received and print it out.
Sorry I don't have time to write and include the code.
Tom Dacon
Dacon Software Consulting
"Tracey" <Tr****@discuss ions.microsoft. com> wrote in message
news:94******** *************** ***********@mic rosoft.com... I have an algorithm question and don't know how to do it nicely. Write a function to print nodes of binary tree, for each leaf node, print
nodes from root node to leaf node. For example, the following binary tree has 4 leaf nodes. 30 25 36 39 40 10 64
The resulting of print should be : 30, 25, 39 30, 25, 40 30, 36, 10 30, 36, 64
This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Jack Smith |
last post by:
Hello, any help appreciated with following problem. I figured out the
algorithm (I think), just having trouble proving it is optimal.
Suppose we are given n tasks each of which takes 1 unit time to
complete. Suppose further that each task has a deadline by which it
is expected to finish. IF a task is not finished by the deadline, a
standard penalty of $10 is applied. The problem is to find a schedule
of the tasks that minimizes the...
|
by: cody |
last post by:
I have to write an algorithm with must ensure that objects are put in
buckets (which are always 4 in size).
The objects have two properties: A and B. It is not allowed that in a bucket
are objects with the same A or B value. But there can be more than one
object with A = null or B = null in the bucket.
Sometimes there is only one valid solution, sometimes there are more valid
solutions, and sometimes there isn't a complete solution at...
|
by: savesdeday |
last post by:
In my beginnning computer science class we were asked to translate a
simple interest problem. We are expected to write an algorithm that
gets values for the starting account balance B, annual interest rate
I, and annual service charge S. Your algorithm would then compute and
print out the total amount of interest earned during the year and the
final account balance at the end of the year (assuming that interest
is compounded monthly, and...
|
by: bpontius |
last post by:
The GES Algorithm
A Surprisingly Simple Algorithm for Parallel Pattern Matching
"Partially because the best algorithms presented in the literature
are difficult to understand and to implement, knowledge of fast and
practical algorithms is not commonplace."
Hume and Sunday, "Fast String Searching", Software - Practice
and Experience, Vol. 21 # 11, pp 1221-48
|
by: Bonj |
last post by:
I was in need of an encryption algorithm to the following requirements:
1) Must be capable of encrypting strings to a byte array, and decyrpting
back again to the same string
2) Must have the same algorithm work with strings that may or may not be
unicode
3) Number of bytes back must either be <= number of _TCHARs in *
sizeof(_TCHAR), or the relation between output size and input size can be
calculated simply. Has to take into account the...
| |
by: FBM |
last post by:
Hi,
I am working on a program that simulates one of the elements of ATM.
The simulation stores events which occurs every some milliseconds for a
certain amount of time. Every time that an event is stored in a double
linked list, the whole list is sorted for the next round.
My problem appears when subjecting the program to heavy load, that is,
when I run the simulation for more than 10,000 miliseconds (every event
occurs in...
|
by: Sherrie Laraurens |
last post by:
Hi all,
I'm trying to write a generic algorithm routine that will
take begin and end iterators of a container, iterate through
the range and perform a "calculation" of sorts.
The trouble is that the algorithm will behave differently for
the two different types. I've considered calling the algorithm
foo_A and foo_B, but I don't like that approach because it will
blow out in naming complexity down the track.
|
by: Julio C. Hernandez Castro |
last post by:
Dear all,
We have just developped a new block cipher called Raiden, following a
Feistel Network structure by means of genetic programming. Our
intention now consists on getting as much feedback as possible from
users, so we encourage you to test the algorithm and send us your
opinion. We would also like to receive enhancements and new versions of
the algorithm, developed in other source languages and platforms.
Our idea on developing...
|
by: Sunway |
last post by:
hello guys i have a bunsh of questions in java and algorithm
most of them i didnt have a problem in them but two i had a diffculty in them could u help me in them please coz its urgent .
the questions are:
Q1.DVD Sales and Shipping Algorithm Design:
You are to design an algorithm to calculate the total cost of a customer order for a number of DVDs. The total is comprised of a component for the DVDs, and also a shipping cost. The costs...
|
by: Dijkstra |
last post by:
Hi folks!
First, this is the code I'm using to expose the problem:
------------------------------------------------------------------
#include <functional>
#include <string>
#include <iostream>
using namespace std;
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
| |
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
| |
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
|
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |