I'm currently messing about (As usual), cooking up an octree (That's a tree containing nodes with up to 8 children) colour quantisation program. The thing is, I'm having trouble getting my head around an integral part of the process. In order to quantize colours in an octree I must seek out nodes that have children that do not have children of their own (The parents of the outermost leaf nodes), e.g.:-
I'm undecided as to whether the function should be recursive or not and this is what I came up with so far:-
Parent <--- Need to find this node
(No children for these nodes, poor little blighters...)
This function is non-recursive and attempts to ascertain whether "parent" is the sort of node I'm looking for by comparing its level or depth in the tree with one I've supplied and also checks the "leaf" member to see if it's greater than 0 (This node has children).
node *FindLowestNodeParent(node *parent, int nLevel)
while (parent->level != nLevel && parent->leaf)
parent = parent->children[i];
Of course, if there are no nodes at that level that fit the profile it'll just return the last one it looked at, which is no good, and although I've tried to combat that behaviour by reducing the level given to the function when the node it returns is the same as the last one processed, it leads to an infinite loop. Octrees can't be easily visualised or represented in text; It's mind-blowing to trace what's going on in a large tree!
Any ideas on an efficient function that returns the next node with "sterile" children, or perhaps NULL if there isn't any?