CODEWITHSUNDEEP
c++algorithmrecursiontree
Michael Eilers Smith
Michael Eilers Smith

Reputation: 8608

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

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!

Upvotes: 5

Views: 4929

Answers (4)

user3069721
user3069721

Reputation: 81

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.

Upvotes: 0

Loki Astari
Loki Astari

Reputation: 264381

Something like this:

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

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

Upvotes: 0

AndersK
AndersK

Reputation: 36082

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*>.

Upvotes: 4

LeleDumbo
LeleDumbo

Reputation: 9340

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.

Upvotes: 0

Related Questions