Thread: recusion in trees

  1. #1
    Registered User
    Join Date
    Jul 2004
    Posts
    91

    recusion in trees

    im trying to implement a calculator
    but the trouble im having is when i have two negative signs should be positive.

    so if i have a tree like
    Code:
       -
      /  \
          -
         /  \
             1
    then the final tree should just be
    Code:
        1
       /  \
    ive been trying to think of an algorithm or a way to code this but.. no luck..

    im thinking it can be done recursively..
    what i have tried to do is..

    1. if root node is a '-'
    2. if root->rightside is a '-'
    3. then create a temp node, which has the root as whatever root->rightside->rightside is. in this case it would be the '1'.
    4. return this new node and then return to top of function and it'll fall into one of the normal cases of just a number and it gets taken care of .. no more worries..


    but will this work if i have more '-'..

    for example
    Code:
       -
      /  \
          -
         / \
              -
             / \
                1
    in this case it should return
    Code:
          -
         / \
            1

    .. any help anybody ?

    Thanks

  2. #2
    Registered User
    Join Date
    Mar 2005
    Posts
    36
    Your problem is probably confusion between subtraction and negative numbers. You resolve the bottom
    Code:
                -
               / \
                  1
    as (0 - 1) or just -1, then the next one up
    Code:
                -
               / \
                  -1
    as (0 - (-1)) or just 1, etc.

    Trying to resolve your tree from the top down will either lead you (recursively) to the bottommost leaves first, or you can start at the bottom level and work across, then up a step, across, up a...
    until nothing is left but a valued root node. You can't resolve a node until its children have been resolved ( for node resolution in a calculator, you replace an operation node by the result of applying the operator to the child nodes - thus by a value - which is possible only if the children are already values, not operators).
    Any attempt to make - - into + will fail in the general (no empty nodes) case because you have ignored, until too late, the values which were supposed to be operated upon. You no longer have enough operators. (- - does not equal + +) Get it?
    Last edited by Karthur; 03-19-2005 at 11:33 PM. Reason: formatting

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Trees
    By masterg in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2008, 01:42 PM
  2. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 02:12 PM
  3. Binary Trees MINI MAXING, probability trees
    By curlious in forum General AI Programming
    Replies: 3
    Last Post: 09-30-2005, 10:57 AM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. AVL Trees
    By kwigibo in forum C Programming
    Replies: 2
    Last Post: 04-17-2002, 05:46 PM