Non-Binary Trees

Discussion in 'C++' started by Will Oram, Oct 27, 2003.

  1. Will Oram

    Will Oram Guest

    Hi,

    My assignment is to create a non-binary tree of arbitrary form, and then
    print out the data in an orderly fashion. The handout contains a tree to
    be inputted:

    2
    / | \
    3 7 5
    / \ |
    1 8 6

    If that 7 weren't there, it would be a binary tree and I could deal with
    it easily. I've searched through texts and notes and the Internet but
    couldn't find any documentation on the subject.

    What's the best way to deal with this situation?

    Thanks.
     
    Will Oram, Oct 27, 2003
    #1
    1. Advertising

  2. Will Oram

    Howard Guest

    "Will Oram" <> wrote in message
    news:...
    > Hi,
    >
    > My assignment is to create a non-binary tree of arbitrary form, and then
    > print out the data in an orderly fashion. The handout contains a tree to
    > be inputted:
    >
    > 2
    > / | \
    > 3 7 5
    > / \ |
    > 1 8 6
    >
    > If that 7 weren't there, it would be a binary tree and I could deal with
    > it easily. I've searched through texts and notes and the Internet but
    > couldn't find any documentation on the subject.
    >
    > What's the best way to deal with this situation?
    >
    > Thanks.


    So what's the problem exactly? Instead of having a left and right child,
    have an array (or vector) of children. Have you done any programming at all
    for this yet? Try taking the code for a binary-tree and modifying it like I
    suggested. Then, if you have an actual C++ problem, come back for more
    specific help.

    -Howard
     
    Howard, Oct 27, 2003
    #2
    1. Advertising

  3. "Will Oram" <> wrote in message
    news:...
    | My assignment is to create a non-binary tree of arbitrary form, and then
    | print out the data in an orderly fashion. The handout contains a tree to
    | be inputted:
    |
    | 2
    | / | \
    | 3 7 5
    | / \ |
    | 1 8 6
    |
    | If that 7 weren't there, it would be a binary tree and I could deal with
    | it easily. I've searched through texts and notes and the Internet but
    | couldn't find any documentation on the subject.

    Wrong NG, e.g. comp.pogramming would be more adequate.
    This said...

    | What's the best way to deal with this situation?

    Every tree can be represented as a binary tree, where:
    - the left node points to the first sibling
    - the right node points to the next brother

    i.e. with left links as | and right links as -- ,
    the following is a binary tree representation of
    the tree you described above:

    2
    |
    3--7--5
    | |
    1--8 6

    You could use this representation to solve your problem.
    Alternatively, you can let each not store a dynamically
    sized list of its siblings (e.g. using std::vector<>),
    or use another representation of a graph or tree (such
    as a matrix of booleans).

    The right solution probably depends on what you
    are / have been studying in class recently.

    Recommended reading: Knuth's TAOCP


    Regards,
    Ivan
     
    Ivan Vecerina, Oct 27, 2003
    #3
  4. While it was 27/10/03 6:18 pm throughout the UK, Will Oram sprinkled
    little black dots on a white screen, and they fell thus:

    > Hi,
    >
    > My assignment is to create a non-binary tree of arbitrary form, and then
    > print out the data in an orderly fashion. The handout contains a tree to
    > be inputted:

    <snip>
    > If that 7 weren't there, it would be a binary tree and I could deal with
    > it easily. I've searched through texts and notes and the Internet but
    > couldn't find any documentation on the subject.


    What are you having trouble with, exactly? The data structure, or the
    orderly fashion? If the latter, we'll need to know what the orderly
    fashion is supposed to look like.

    Stewart.

    --
    My e-mail is valid but not my primary mailbox. Please keep replies on
    on the 'group where everyone may benefit.
     
    Stewart Gordon, Oct 28, 2003
    #4
    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:
    747
    Roedy Green
    Apr 26, 2004
  2. JC

    Binary trees

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

    Binary Trees

    jova, Apr 25, 2004, in forum: C++
    Replies:
    11
    Views:
    783
    Roedy Green
    Apr 26, 2004
  4. Joe Seigh

    Lock-free binary trees

    Joe Seigh, Jul 2, 2006, in forum: Java
    Replies:
    27
    Views:
    1,454
    Chris Thomasson
    Jul 16, 2006
  5. jacob navia

    Binary search trees (AVL trees)

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

Share This Page