CODEWITHSUNDEEP
calgorithmdata-structurestree
StarShire
StarShire

Reputation: 309

How to create a tree where it finds the correct node to add the children node?

What's the best way to build a tree where the input gives the format (a,b), a is the parent node and b is the children node? (node 1 is the root) For example:

1 2 //adds node #2 as the children of #1 (the root)
1 3 //adds node #3 as the second children of the root
2 4 //adds node #4 as the children of node #2
etc...

I understand how to make this kind of tree if it is like a binary tree (since the left child is the lesser value and the right child is the the greater for a given parent node). But, the amount of children nodes a parent can have is not fixed for my tree. How can I create this efficiently? I'm having trouble understanding how the algorithm can iterate and find the correct node (the a part of the input) so that it can add another node as the children (the b part of the input) since the amount of children a node can have isn't fixed.

EDIT: Another thing I want to add: each leaf nodes (ones with no children nodes) will be assigned some values. I need to recursively (or some other method) traverse down the tree so that I can calculate the values of each node: the parent node value is the sum of all of its children node values.

Upvotes: 0

Views: 245

Answers (2)

mrd abd
mrd abd

Reputation: 858

store Right child and sibling addresses in each node.

when you receive a,b, if node a has not right child insert b as right child and if has right child follow the sibling of right child to find last child and insert b as sibling of the last node.

Traversing the tree:

I think this algorithm can traverse the tree in Depth First:

traverse(Node) 
 visit (Node) // pre order 
 if (Node.RightChild != Null)
  n = Node.RightChild
  while(n.LeftSibling != Null)
   traverse ( n.LeftSibling )
   n = n.LeftSibling
  end
 end
end

Upvotes: 0

Bernhard Barker
Bernhard Barker

Reputation: 55619

It's usually sufficient to store children nodes as a linked-list (or array) (although, depending on the type of tree, other representations may be more efficient).

Typically you'd have a map or array of nodes.

When you're looking for a, you'd simply do a lookup in the map or array for it.

Then you simply add b to the list of children.

I need to recursively traverse down the tree

That would involve a simple breadth-first search or depth-first search.

Upvotes: 0

Related Questions