473,320 Members | 2,122 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

recursive

jw
i have a b.tree that has a prefix expression like this->+ x 2 - 5 1 x 3
2

if i use this recursive function it prints ((2x(5-1))+(3x2))

void printTree(t)
if(t.left!=NULL)
print("(");
printTree(t.left);
print(t.element);
if(t.right!=NULL)
printTree(t.right);
print(")");
can you explain why it prints ((2x(5-1))+(3x2))

Jan 24 '06 #1
11 2674
jw wrote:
i have a b.tree that has a prefix expression like this->+ x 2 - 5 1 x 3
2
How does your "b.tree" _have_ that expression?
if i use this recursive function it prints ((2x(5-1))+(3x2))

void printTree(t)
if(t.left!=NULL)
print("(");
printTree(t.left);
print(t.element);
if(t.right!=NULL)
printTree(t.right);
print(")");
can you explain why it prints ((2x(5-1))+(3x2))


It prints what it's asked to print, apparently. Since you don't show how
you form the tree from your prefix expression, there is no way to tell if
the function actually does the right thing or not.

V
Jan 24 '06 #2
jw
root=+
root->right=x x->left=3 x->right=2
root->left=x x->left=2 x->right=- - ->left=5
- ->right1

Jan 24 '06 #3
jw wrote:
root=+
root->right=x x->left=3 x->right=2
root->left=x x->left=2 x->right=- - ->left=5
- ->right1


So, as I get it, it's like this

.. [ + ]
.. / \
.. [ x ] [ x ]
.. / \ / \
.. [ 2 ] [ - ] [ 3 ] [ 2 ]
.. / \
.. [ 5 ] [ 1 ]

What should it print? First it takes the root, right? Then it sees that
the left (the 'x') is not NULL. So, it prints the parenthesis first, and
then the left tree. How? What does it mean to print a tree when the left
'x' is now a temporary root? It looks at its left. It's not NULL (it's
the leftmost '2'), so it prints another parenthesis, and then the subtree
where the leftmost '2' is the new root. How? Its left is NULL, its
'element' is "2", and its right is NULL. Then it returns. Where? To
print the rest of the left 'x' subtree. How? It prints the element, it's
"x", then it see that the right is not NULL. It prints the right subtree
(with the '-' as its root). How? ...

Continue until you finish printing the right part of the '+'.

I don't see any C++ question, by the way. Next time post to a newsgroup
where your general programming question is more topical, comp.programming.

V
Jan 24 '06 #4

jw wrote:
i have a b.tree that has a prefix expression like this->+ x 2 - 5 1 x 3
2

if i use this recursive function it prints ((2x(5-1))+(3x2))

void printTree(t)
if(t.left!=NULL)
print("(");
printTree(t.left);
print(t.element); .... can you explain why it prints ((2x(5-1))+(3x2))


A miracle occured.

Jan 24 '06 #5
jw
how does it return to x after printing 2?

Jan 25 '06 #6

"jw" <ja*****@gmail.com> wrote in message
how does it return to x after printing 2?


Look at your code:

void printTree(t)
if(t.left!=NULL)
print("(");
printTree(t.left);
print(t.element);
if(t.right!=NULL)
printTree(t.right);
print(")");

It prints the left: "(" + "2", then itself: "x", then the right: "(5-1)" +
")".

(By the way, it would really help if you'd quote the relevant parts of
previous replies, so we can see what you're talking about without having to
look at other posts.)

-Howard
Jan 25 '06 #7
jw

Howard wrote:
"jw" <ja*****@gmail.com> wrote in message
how does it return to x after printing 2?
Look at your code:

void printTree(t)
if(t.left!=NULL)
print("(");
printTree(t.left);
print(t.element);
if(t.right!=NULL)
printTree(t.right);
print(")");

It prints the left: "(" + "2", then itself: "x", then the right: "(5-1)" +
")".

ok but after this how does it return to the real root the print the
rightmost.
(By the way, it would really help if you'd quote the relevant parts of
previous replies, so we can see what you're talking about without having to
look at other posts.)

-Howard


Jan 25 '06 #8
"jw" <ja*****@gmail.com> wrote in message
news:11**********************@g43g2000cwa.googlegr oups.com...
i have a b.tree that has a prefix expression like this->+ x 2 - 5 1 x 3
2

if i use this recursive function it prints ((2x(5-1))+(3x2))

void printTree(t)
if(t.left!=NULL)
print("(");
printTree(t.left);
print(t.element);
if(t.right!=NULL)
printTree(t.right);
print(")");
can you explain why it prints ((2x(5-1))+(3x2))


.. [ + ]
.. / \
.. [ x ] [ x ]
.. / \ / \
.. [ 2 ] [ - ] [ 3 ] [ 2 ]
.. / \
.. [ 5 ] [ 1 ]

Well, just follow the logic. I presume you first call printTree by passing
it the root. Then printTree looks to see if there is a left brance, and
there is (the x). It prints a "(" and it calls printTree on the x.
printTree then looks to see if there is a left, and there is, the 2. It
prints a "(" and calls printTree on the 2. printTree looks to see if there
is a left on the 2, there isn't. It then prints the element 2. It looks to
see if there is a right branch on the 2, there isn't. So it returns (now
we're back where the x was). printTree prints the element x (so far we have
((2x ) It then looks for the right branch, there is one, it calls printTree
for the element -, etc...

It is recursion. You need to follow it through and remember what element
you are dealing with.
Jan 25 '06 #9
jw wrote:
how does it return to x after printing 2?


OK, guys, from this it's most likely homework.
Jan 25 '06 #10

red floyd wrote:
jw wrote:
how does it return to x after printing 2?


OK, guys, from this it's most likely homework.


And it is riddled with syntax errors...thing doesn't even compile, let
alone print anything.

Jan 25 '06 #11

"jw" <ja*****@gmail.com> wrote in message
Look at your code:

void printTree(t)
if(t.left!=NULL)
print("(");
printTree(t.left);
print(t.element);
if(t.right!=NULL)
printTree(t.right);
print(")");

It prints the left: "(" + "2", then itself: "x", then the right: "(5-1)"
+
")".

ok but after this how does it return to the real root the print the
rightmost.


If you can't figure it out by now, ask your teacher for help.

-Howard

Jan 25 '06 #12

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

19
by: Carlos Ribeiro | last post by:
Hello all, Here I am using some deeply nested, tree-like data structures. In some situations I need to traverse the tree; the old-style way to do it is to write a recursive method on the node...
10
by: Steve Goldman | last post by:
Hi, I am trying to come up with a way to develop all n-length permutations of a given list of values. The short function below seems to work, but I can't help thinking there's a better way. ...
2
by: | last post by:
OK: Purpose: Using user's input and 3 recursive functions, construct an hour glass figure. Main can only have user input, loops and function calls. Recursive function 1 takes input and displays...
7
by: Jon Slaughter | last post by:
#pragma once #include <vector> class empty_class { }; template <int _I, int _J, class _element, class _property> class RDES_T {
1
by: Jon Slaughter | last post by:
I've managed to put together a template class that basicaly creates a recursive tree that lets you easily specify the "base" class of that tree and and ending notes and lets you stop the recursive...
4
by: Victor | last post by:
Hello, I've got a situation in which the number of (valid) recursive calls I make will cause stack overflow. I can use getrlimit (and setrlimit) to test (and set) my current stack size. ...
9
by: seberino | last post by:
I'm a compiler newbie and curious if Python grammar is able to be parsed by a recursive descent parser or if it requires a more powerful algorithm. Chris
0
by: champ1979 | last post by:
I wrote an algorithm to get all the relatives of a person in a family tree. I'm basically getting all the users from the DB and am doing the recursive logic in code, so that there is only 1 call...
18
by: Just Another Victim of the Ambient Morality | last post by:
Is pyparsing really a recursive descent parser? I ask this because there are grammars it can't parse that my recursive descent parser would parse, should I have written one. For instance: ...
3
by: from.future.import | last post by:
Hi, I encountered garbage collection behaviour that I didn't expect when using a recursive function inside another function: the definition of the inner function seems to contain a circular...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
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...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 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 former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.