Binary trees

Discussion in 'C Programming' started by n.noumia@gmail.com, May 4, 2007.

  1. Guest

    - with 10 nodes, give one example of an unbalanced binary tree and
    one example of a balanced binary tree
    - what is the advantage of having a balanced binary tree over an
    unbalanced tree?
    - number your nodes, then give the order in which nodes will be
    visited by a depth-first-search
    - explain the differences between traversing the tree pre-order, in-
    order and post-order
     
    , May 4, 2007
    #1
    1. Advertising

  2. In article <>,
    <> wrote:
    > - with 10 nodes, give one example of an unbalanced binary tree and
    >one example of a balanced binary tree


    Example of a balanced binary tree: [IMAGE]
    Example of an unbalanced binary tree: [IMAGE]

    > - what is the advantage of having a balanced binary tree over an
    >unbalanced tree?


    A balanced tree won't fall over when you stop holding it.

    > - number your nodes, then give the order in which nodes will be
    >visited by a depth-first-search


    42, pi, 17, e, 105, 69, i, sqrt(2), 3, -1.

    > - explain the differences between traversing the tree pre-order, in-
    >order and post-order


    The order you traverse it in is different.

    DYODH.



    dave

    --
    Dave Vandervies
    Hey, I can beat him on the Impressive But Useless certificates thing.
    I have a PhD.
    --Dan Holdsworth in the scary devil monastery
     
    Dave Vandervies, May 4, 2007
    #2
    1. Advertising

  3. Eric Sosman Guest

    wrote:
    > - with 10 nodes, give one example of an unbalanced binary tree and
    > one example of a balanced binary tree


    Unbalanced tree: AB,C'K:D'EH:FJ:G: (notation adapted
    from Knuth, TAOCP 2.3.3 equation 3)

    To balance the tree, put another one on the other pan.

    > - what is the advantage of having a balanced binary tree over an
    > unbalanced tree?


    Easier access to firewood. When the next high wind topples
    the unbalanced tree, the balanced tree that's over it will fall
    at the same time and save you the work of cutting it down.

    > - number your nodes, then give the order in which nodes will be
    > visited by a depth-first-search


    Numbers: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

    Depth-first order: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

    > - explain the differences between traversing the tree pre-order, in-
    > order and post-order


    With pre-order, the pizza is ready when you arrive at the
    shop and you needn't wait. With in-order, you may need to pay
    a restaurant tax to eat the pizza on the premises. With post-
    order, the pizza reaches you three to five business days later
    and is unpalatable.

    --
    Eric Sosman
    lid
     
    Eric Sosman, May 4, 2007
    #3
  4. Chris Dollin Guest

    wrote:

    > - with 10 nodes, give one example of an unbalanced binary tree and
    > one example of a balanced binary tree
    > - what is the advantage of having a balanced binary tree over an
    > unbalanced tree?
    > - number your nodes, then give the order in which nodes will be
    > visited by a depth-first-search
    > - explain the differences between traversing the tree pre-order, in-
    > order and post-order


    I think you should have posted to comp.lazy.domyhomework, since (a)
    this is homework; having someone else do it for you misses the point;
    (b) it's off-topic, since it isn't about C at all.

    --
    Not A Number, A Free Hedgehog
    Meaning precedes definition.
     
    Chris Dollin, May 4, 2007
    #4
  5. wrote:
    > - with 10 nodes, give one example of an unbalanced binary tree and
    > one example of a balanced binary tree

    http://en.wikipedia.org/wiki/Binary_tree

    > - what is the advantage of having a balanced binary tree over an
    > unbalanced tree?

    A balanced tree will not fall over in a storm, as long as the wind blows
    evenly from all directions.

    > - number your nodes, then give the order in which nodes will be
    > visited by a depth-first-search

    http://en.wikipedia.org/wiki/Binary_tree#Depth-first_order

    > - explain the differences between traversing the tree pre-order, in-
    > order and post-order
    >

    http://en.wikipedia.org/wiki/Binary_tree#Pre-order.2C_in-order.2C_and_post-order_traversal.

    --
    clvrmnky

    Direct replies will be blacklisted. Replace "spamtrap" with my name to
    contact me directly.
     
    Clever Monkey, May 4, 2007
    #5
  6. In article <6NI_h.7930$!nnrp1.uunet.ca>,
    Clever Monkey <> wrote:
    > wrote:


    >> - what is the advantage of having a balanced binary tree over an
    >> unbalanced tree?

    >A balanced tree will not fall over in a storm, as long as the wind blows
    >evenly from all directions.


    But the wind in most storms doesn't blow evenly from all directions.
    If you're going for storm tolerance, you really want an unbalanced tree,
    but the problem with that is that every time the wind changes you have
    to go out and re-unbalance it for the new wind direction.


    dave

    --
    Dave Vandervies
    And there was nothing insulting about it. Some people would rather
    take being called a ``normal person'' as an insult.
    --Nils Goesche in comp.lang.c
     
    Dave Vandervies, May 4, 2007
    #6
  7. In article <>,
    Eric Sosman <> wrote:
    > wrote:
    >> - with 10 nodes, give one example of an unbalanced binary tree and
    >> one example of a balanced binary tree

    >
    > Unbalanced tree: AB,C'K:D'EH:FJ:G: (notation adapted
    >from Knuth, TAOCP 2.3.3 equation 3)


    Unless you have a different edition than I do (3rd), I think you meant
    equation 4.


    dave

    --
    Dave Vandervies
    The DS 9000 is a conforming implementation.
    The DS 9001 is so cleverly designed that experts can't agree whether it
    is conforming or not! --Christian Bau in comp.lang.c
     
    Dave Vandervies, May 4, 2007
    #7
  8. Eric Sosman Guest

    Dave Vandervies wrote On 05/04/07 16:08,:
    > In article <>,
    > Eric Sosman <> wrote:
    >
    >> wrote:
    >>
    >>> - with 10 nodes, give one example of an unbalanced binary tree and
    >>>one example of a balanced binary tree

    >>
    >> Unbalanced tree: AB,C'K:D'EH:FJ:G: (notation adapted

    >
    >>from Knuth, TAOCP 2.3.3 equation 3)

    >
    > Unless you have a different edition than I do (3rd), I think you meant
    > equation 4.


    The renumbering was part of the adaptation.

    --
     
    Eric Sosman, May 4, 2007
    #8
  9. Dave Vandervies wrote:
    > In article <6NI_h.7930$!nnrp1.uunet.ca>,
    > Clever Monkey <> wrote:
    >> wrote:

    >
    >>> - what is the advantage of having a balanced binary tree over an
    >>> unbalanced tree?

    >> A balanced tree will not fall over in a storm, as long as the wind blows
    >> evenly from all directions.

    >
    > But the wind in most storms doesn't blow evenly from all directions.
    > If you're going for storm tolerance, you really want an unbalanced tree,
    > but the problem with that is that every time the wind changes you have
    > to go out and re-unbalance it for the new wind direction.
    >

    So true. I think I'm barking up the wrong tree here. We better leaf
    this alone for while, or we might end up branching off into the wrong
    direction. If I twig onto anything else, I'll let you know, but I think
    this conversation will not bear any new fruit. Either that, or I'm the
    fall guy and can't see the tree for the forest.

    --
    clvrmnky

    Direct replies will be blacklisted. Replace "spamtrap" with my name to
    contact me directly.
     
    Clever Monkey, May 4, 2007
    #9
    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. jova

    Binary Trees

    jova, Apr 25, 2004, in forum: Java
    Replies:
    11
    Views:
    745
    Roedy Green
    Apr 26, 2004
  2. Will Oram

    Non-Binary Trees

    Will Oram, Oct 27, 2003, in forum: C++
    Replies:
    3
    Views:
    718
    Stewart Gordon
    Oct 28, 2003
  3. JC

    Binary trees

    JC, Dec 8, 2003, in forum: C++
    Replies:
    6
    Views:
    594
    osmium
    Dec 10, 2003
  4. jova

    Binary Trees

    jova, Apr 25, 2004, in forum: C++
    Replies:
    11
    Views:
    780
    Roedy Green
    Apr 26, 2004
  5. jacob navia

    Binary search trees (AVL trees)

    jacob navia, Jan 3, 2010, in forum: C Programming
    Replies:
    34
    Views:
    1,440
    Dann Corbit
    Jan 8, 2010
Loading...

Share This Page