Tree structure - Gideros Forum

#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

#### Top Posters

• ar2rsawseen 6991
• SinisterSoft 3812
• hgy29 2461
• keszegh 2055
• antix 2033
• OZApps 1983
• totebo 1764
• oleg 1574
• hgvyas123 1412
• techdojo 1321
• phongtt 1029
• Mells 1024
• MikeHart 1020
• john26 995
• GregBUG 962
• pie 960
• talis 908
• Scouser 898
• Apollo14 868
• MoKaLux 840

# Tree structure

edited June 26
I have a small problem, that I cant solve for whatever reason.

I have a tree that looks like this: Where red dots - unavailable nodes, green dots - available nodes, purple dots - nodes with childs. Basic node structure:
 `{id = "whatever", available = false, parent = ..., childs= {...}}`
Now the fun part. Somehow I manage to get to node with id=10 (by clicking on it or maybe loop over whole tree, it does not matter). And I know all information about this node. Now I need to look for the next possible green node. It must be 17, then 19, 16 and so on.

The simple solution is to brute force whole tree like this:
 ```local currentNode = ... local found = false   function bruteForce(node) for i,subNode in ipairs(node.childs) do -- found current if subNode == currentNode then found = true -- next posible is found elseif found and subNode.available then found = false return subNode end -- check childs if #subNode.childs > 0 then local n = bruteForce(subNode) if n then return n end end end end   bruteForce(root)```
But I dont like it. There must be a better way Any ideas?
Tagged:

• edited June 26 you should also store the parent of a node and then you can start with the currentNode and traverse the tree in depth-first search (dfs) manner from there (as it seems that's what you want). search for dfs and tree data structures e.g. https://brilliant.org/wiki/depth-first-search-dfs/ .

btw if you don't intend to modify the tree then you can preprocess it with a dfs once and build a 'next node' table from which you can get the next node immediately. you can even update this table when a new node is added to the tree.
• keszegh said:

you should also store the parent of a node

keszegh said:

and then you can start with the currentNode and traverse the tree in depth-first search (dfs) manner from there (as it seems that's what you want). search for dfs and tree data structures e.g. https://brilliant.org/wiki/depth-first-search-dfs/ .

I know how to do this. I understand how to work with trees.
Thats what I have and it gives me correct results.
 ```function findFirstPosible(node) for i,c in ipairs(node.childs) do if c.available then return c else local f = findFirstPosible(c) if f then return f end end end end```
The problem is how you can get from node 16 to 6?
keszegh said:

btw if you don't intend to modify the tree then you can preprocess it with a dfs

Not my case • 16->6: well, only way is to continue dfs search, which will go up via parents to root first, and then go down to 6.
• keszegh said:

to root first

If it comes to root I will get 10. Cuz its first valid answer.

• well, when from node A you go up one level to a node B you need to 'remember' where you came from (that is, A) and from B you have to go to a child that is the 'next' one after A in the order of children of B. and if there is no such child (i.e., A was the 'last' child of then you go from B to the parent of B.
then you repeat the same process now with B instead of A. and you repeat this process until you find a green leaf.
• keszegh said:

well, when from node A you go up one level to a node B you need to 'remember' where you came from (that is, A) and from B you have to go to a child that is the 'next' one after A in the order of children of B. and if there is no such child (i.e., A was the 'last' child of then you go from B to the parent of B.
then you repeat the same process now with B instead of A. and you repeat this process until you find a green leaf. Sure that will work but I dont know how to code it ))) I tried various different implementations, recursive/while loops and it just does not work • what i wrote is almost pseudo-code, give it a try, i think you will succeed.
• do a next_using_dfs() function which from A finds B in the way i wrote.
and then you do not need recursion, just keep calling this on the new node it gives until you get a green node.
• so next_using_dfs(16) will find give 12, then next_using_dfs(12) will give 5 and so on.
• and i cheated a bit, as i wrote you need to remember 'previous place', so next_using_dfs() should have two inputs (except when you call it on a leaf, the first time).
so you first call next_using_dfs(16) then run next_using_dfs(12,16) then next_using_dfs(5,12) and so on.
• even better, make a function which from a node either points to the next child of its parent or if he is the last child then points to its parent.
and then you don't need two inputs, this function finds what you want by repeated calls.
• edited June 27
Finally I did it! @keszegh ty for help!

I guess it can be optimized but for now its ok.
 ```-- main function function getNext(node) -- try to find node in current group local nextNode = findNext(node) if nextNode then return nextNode -- if does not exist else -- go up local b = goBack(node) if b then return b else -- this is the last node, so we need to -- wrap to first possible node of the root return findFirstPosible(root) end end end -- function goBack(node) local curr = node.__owner --< get parent of the node if not curr then return end   local prev = curr.__owner --< get parent of a "curr" node if not prev then return end   local n = prev:getNodeCount() --< number of childs   local ind = prev:getNodeIndex(curr) --< get index in tree if ind + 1 <= n then --< if next node exist -- pick this next node local nextToCurr = prev:getNodeAt(ind+1) -- if this node is valid return it if nextToCurr.valid then return nextToCurr end   -- if not check its childs local nextNode = findFirstPosible(nextToCurr) -- if found something return it if nextNode then return nextNode else nextNode = findNext(nextToCurr) if nextNode then return nextNode end -- go up return goBack(curr) end else -- go up return goBack(curr) end end -- start from current node+1 and find first valid node -- if not found in current group, go deeper function findNext(node) local owner = node.__owner if not owner then return end   local ind = owner:getNodeIndex(node) for i = ind + 1, owner:getNodeCount() do local n = owner:getNodeAt(i) if n.valid then return n else -- go deeper n = findFirstPosible(n) if n then return n end end end end -- function findFirstPosible(node) for i = 1, node:getNodeCount() do local n = node:getNodeAt(i) if n.valid then return n else n = findFirstPosible(n) if n then return n end end end end```

Now I need same thing but In opposite direction Likes: MoKaLux

+1 -1 (+1 / -0 ) Share on Facebook
• this may interest you?
http://forum.giderosmobile.com/discussion/comment/63302/#Comment_63302 my growING GIDEROS github repositories: https://github.com/mokalux?tab=repositories
• edited June 27
MoKaLux said:

this may interest you?
http://forum.giderosmobile.com/discussion/comment/63302/#Comment_63302 Probably not Im still trying to create a UI lib This is 6th generation so far xD Rewritten almost from scratch about a week ago. P.S. the gfx taken from godot engine.
+1 -1 (+3 / -0 ) Share on Facebook
• edited June 27
Go backwards
 ```function getPrev(node) local prevNode = findLast(node) if prevNode then return prevNode end   local b = goUpBackward(node) if b then return b end   return findLastPosible(root) end -- function goUpBackward(node) local currRoot = node.__owner if not currRoot then return end   local ind = currRoot:getNodeIndex(node) if ind - 1 > 0 then local prev = currRoot:getNodeAt(ind-1) if prev.valid then return prev end   local last = findLast(prev) if last then return last end   last = findLastPosible(prev) if last then return last end end return goUpBackward(currRoot) end -- function findLast(node) local owner = node.__owner if not owner then return end local ind = owner:getNodeIndex(node) for i = ind - 1,1,-1 do local c = owner:getNodeAt(i) if c.valid then return c end c = findLastPosible(c) if c then return c end end end -- function findLastPosible(node) for i = node:getNodeCount(), 1, -1 do local c = node:getNodeAt(i) if c.valid then return c end c = findLastPosible(c) if c then return c end end end```
• congratulations.