1

this is my first post on Stack Overflow. I really admire the site and all the users who help the others code a lot. Hopfully I can get some help from you:)

The problem I have met can be described as follows:

  1. Start from a given node(root node);
  2. Calculate the children of the node and store them(the number of the children is not known before calculating);
  3. At the leaf node, calculate the value of the leaf using 'evaluate function'.
  4. When all the leaves are evaluated, choose the leaf node which has largest/smallest value and get the data stored in this leaf's grandfather(child of root) as showed in picture.

Process of traverse and build a tree:

Process of traverse and build a tree

As the 'evaluate function' can only be applied at leaf node, I think depth-first search is suitable here. What's more, the MATLAB Function Block in Simulink doesn't support calling function recursively. So I think using Stack to store the node is a good way.

According to the excellent answers here, the logic is quite clear and straight forward. Code from Gumbo

stack.push(root)
while !stack.isEmpty() do
  node = stack.pop()
  for each node.childNodes do
    stack.push(stack)
  endfor
// …
endwhile

But I met some problems when I implemented the DFS algorithm:

  1. As Adjacency matrix wastes a lot of memory, I tried to use adjacency list to represent the tree. But I didn't even find a pseudo code using adjacency list to implement DFS algorithm. Could someone help me?

  2. How can I update the tree when new nodes a calculated from parent(adding nodes)?

  3. Should I let the children inherit the data from the grandfather(children of root) to spare the tracing-back-step? Is there other way to solve 4th step of the process?

Community
  • 1
  • 1
Kevin
  • 21
  • 6
  • Are you calculating the children of all of the nodes, not just the root? If so, then I don't see why you need an adjacency list/matrix at all; just push the calculated nodes onto the stack. – beaker Dec 03 '16 at 16:47
  • @beaker You are right! In my case I don't even need a list to mark the nodes that are visited. A stack can fullfill all I need. Thank you! – Kevin Dec 08 '16 at 14:26

0 Answers0