Non-Binary Trees

[Will Oram]

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.

 

[Howard]

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

 

[Ivan Vecerina]

| 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

 

[Stewart Gordon]

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:

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.