recursive

Discussion in 'C++' started by jw, Jan 24, 2006.

  1. jw

    jw Guest

    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))
    jw, Jan 24, 2006
    #1
    1. Advertising

  2. 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
    Victor Bazarov, Jan 24, 2006
    #2
    1. Advertising

  3. jw

    jw Guest

    root=+
    root->right=x x->left=3 x->right=2
    root->left=x x->left=2 x->right=- - ->left=5
    - ->right1
    jw, Jan 24, 2006
    #3
  4. 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
    Victor Bazarov, Jan 24, 2006
    #4
  5. jw

    Guest

    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, 2006
    #5
  6. jw

    jw Guest

    how does it return to x after printing 2?
    jw, Jan 24, 2006
    #6
  7. jw

    Howard Guest

    "jw" <> 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
    Howard, Jan 25, 2006
    #7
  8. jw

    jw Guest

    Howard wrote:
    > "jw" <> 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
    jw, Jan 25, 2006
    #8
  9. jw

    Jim Langston Guest

    "jw" <> wrote in message
    news:...
    >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.
    Jim Langston, Jan 25, 2006
    #9
  10. jw

    red floyd Guest

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


    OK, guys, from this it's most likely homework.
    red floyd, Jan 25, 2006
    #10
  11. jw

    Guest

    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, 2006
    #11
  12. jw

    Howard Guest

    "jw" <> 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
    Howard, Jan 25, 2006
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Anand P Paralkar

    NCVHDL/NCELAB and Recursive Instantiation

    Anand P Paralkar, Nov 10, 2003, in forum: VHDL
    Replies:
    2
    Views:
    3,019
    Mike Treseler
    Nov 10, 2003
  2. Joerg Ritter
    Replies:
    10
    Views:
    2,203
    Marcin
    Dec 6, 2003
  3. Tyron

    Recursive function

    Tyron, Apr 16, 2004, in forum: VHDL
    Replies:
    1
    Views:
    619
    valentin tihomirov
    Apr 16, 2004
  4. n00m
    Replies:
    12
    Views:
    1,103
  5. vamsi
    Replies:
    21
    Views:
    2,051
    Keith Thompson
    Mar 9, 2009
Loading...

Share This Page