How to build a non-binary tree with or without recursion?

Question

I have a hierarchical data that goes like this:

+----------------------+-------+
| name                 | depth |
+----------------------+-------+
| ELECTRONICS          |     0 |
| TELEVISIONS          |     1 |
| TUBE                 |     2 |
| LCD                  |     2 |
| PLASMA               |     2 |
| PORTABLE ELECTRONICS |     1 |
| MP3 PLAYERS          |     2 |
| FLASH                |     3 |
| CD PLAYERS           |     2 |
| 2 WAY RADIOS         |     2 |
+----------------------+-------+

TUBE, LCD and PLASMA are children of TELEVISIONS. FLASH is the child of MP3 PLAYERS. MP3 PLAYERS, CD PLAYERS and 2 WAY RADIOS are the children of PORTABLE ELECTRONICS. You get the drill.

Now, I have a structure Node that contains its Id and its children, and so on, as to build a tree. Like this:

struct Node
{
   int id;
   list<Node*> children;
}

Each item is identified by an ID, which is the row number (ELECTRONICS=0, TELEVISIONS=1, and so on), so it is easy to find out who are the children of a node.

This is the tree I'm trying to build. This tree is not binary, as you can see. So applying recursion doesn't seem like an easy idea. Correct me if I'm wrong.

So how can I perform this? Help!

Recursion makes it easier where you have more than 1 path to explore. Thus 2 or more branches makes recursion the easy choice. The alternative approach (iteration) requires you to manually keep track of your progresses (ie do the work that the stack is doing in the recursive version). But for this situation recursion is not needed. — Loki Astari
– Loki Astari, Commented Jan 30, 2012 at 6:41

AndersK · Accepted Answer · 2012-01-30 06:36:33Z

4

You should use pointers to Nodes instead, otherwise you will be duplicating data in your tree in each level.

I would also suggest you use an enum instead of int id, it makes the code a bit more clearer.

there is no problem using recursion with a non-binary tree, you just need to instead of calling left/right (or similar) in your recursive function call each in the list<Node*>.

answered Jan 30, 2012 at 6:36

AndersK

36.1k6 gold badges64 silver badges86 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Marcel Valdez Orozco Over a year ago

It's probably better to use a Hash instead of a list, since access time will be constant, whereas in a list its O(n) (by definition).

LeleDumbo · Accepted Answer · 2012-01-30 06:33:19Z

0

There's no limitation that the tree should be binary in order to build it recursively. It could be both created both with recursive and non-recursive method.

For me, I would build the tree in a top down fashion, i.e. create the parent node before the children. I would sort the input data somehow to make the consumption linear. To add a new node, just give depth as parameter and decrease (while going down from root) until it reaches 0, that's where the node should be. Of course, information of parent path for the node is required.

answered Jan 30, 2012 at 6:33

LeleDumbo

9,3804 gold badges26 silver badges38 bronze badges

1 Comment

Michael Eilers Smith Over a year ago

I don't see how this would work. Could you give me a snippet of code?

Loki Astari · Accepted Answer · 2012-01-30 06:47:16Z

0

Something like this:

int main()
{
    Node  flash(FLASH_ID);
    Node  mp3(MP3_ID);

    mp3.children.push_back(flash);
    // repeat
}

answered Jan 30, 2012 at 6:47

Loki Astari

267k87 gold badges344 silver badges575 bronze badges

Comments

user3069721 · Accepted Answer · 2013-12-05 11:00:11Z

0

You can use more than one linking pointer. i.e.

struct node
{
int id;
node *first_child;
node *second child;
node *third_child;
}

In you case the maximum is 3. You can point nodes with the different children and access them. In case, there are less than 3 children, you can make it NULL.

answered Dec 5, 2013 at 11:00

user3069721

811 silver badge3 bronze badges

Collectives™ on Stack Overflow

How to build a non-binary tree with or without recursion?

4 Answers 4

1 Comment

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related