Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > recursive

Reply
Thread Tools

recursive

 
 
jw
Guest
Posts: n/a
 
      01-24-2006
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))

 
Reply With Quote
 
 
 
 
Victor Bazarov
Guest
Posts: n/a
 
      01-24-2006
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
 
Reply With Quote
 
 
 
 
jw
Guest
Posts: n/a
 
      01-24-2006
root=+
root->right=x x->left=3 x->right=2
root->left=x x->left=2 x->right=- - ->left=5
- ->right1

 
Reply With Quote
 
Victor Bazarov
Guest
Posts: n/a
 
      01-24-2006
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
 
Reply With Quote
 
roberts.noah@gmail.com
Guest
Posts: n/a
 
      01-24-2006

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.

 
Reply With Quote
 
jw
Guest
Posts: n/a
 
      01-24-2006
how does it return to x after printing 2?

 
Reply With Quote
 
Howard
Guest
Posts: n/a
 
      01-25-2006

"jw" <(E-Mail Removed)> 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


 
Reply With Quote
 
jw
Guest
Posts: n/a
 
      01-25-2006

Howard wrote:
> "jw" <(E-Mail Removed)> 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


 
Reply With Quote
 
Jim Langston
Guest
Posts: n/a
 
      01-25-2006
"jw" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) 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.


 
Reply With Quote
 
red floyd
Guest
Posts: n/a
 
      01-25-2006
jw wrote:
> how does it return to x after printing 2?
>


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

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Recursive functions Vs Non-recursive functions - performance aspect vamsi C Programming 21 03-09-2009 10:53 PM
Two recursive calls inside of a recursive function n00m C++ 12 03-13-2008 03:18 PM
Recursive function Tyron VHDL 1 04-16-2004 07:20 AM
recursive description with generate and processes Joerg Ritter VHDL 10 12-06-2003 10:24 PM
NCVHDL/NCELAB and Recursive Instantiation Anand P Paralkar VHDL 2 11-10-2003 06:14 PM



Advertisments