"Which parent has children with no children"?!?

Hello,

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

Code:

---

    Parent  <--- Need to find this node
    /          \
Child    Child
(No children for these nodes, poor little blighters...)

---

I'm undecided as to whether the function should be recursive or not and this is what I came up with so far:-

Code:

---

node *FindLowestNodeParent(node *parent, int nLevel)
{
        int i;

        while (parent->level != nLevel && parent->leaf)
        {
                for (i=0;i<8;i++)
                {
                        if (parent->children[i])
                        {
                                parent = parent->children[i];
                                break;
                        }

                }

        }

        return parent;
}

---

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

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! :eek:

Any ideas on an efficient function that returns the next node with "sterile" children, or perhaps NULL if there isn't any?

it can be done easily.. but if it is a simple program you are workin on how about maintainin one more pointer in each node which has its parent address strored... By this when you find a node with no child you just need to get the node->parent to do your operation...

I was bored, so I wrote this example.

Code:

---

#include <stdio.h>
#include <stdlib.h>

typedef struct NODE
{
  struct NODE *leaf;
  int i;
} NODE;

NODE *newnode(int num)
{
  NODE *temp = malloc(sizeof(*temp));
  temp->i = num;
  temp->leaf = NULL;
  return temp;
}

NODE *FindLowestNodeParent(NODE *head)
{
  while (head && head->leaf && head->leaf->leaf)
    head = FindLowestNodeParent(head->leaf);
 
  return head;
} 
 
int main(void)
{
  int i;
  NODE *head = newnode(0);
  NODE *temp = head;
 
  for (i = 0; i < 10; i++)
  {
    temp->leaf = newnode(i+1);
    temp = temp->leaf;
  }

  puts ("The list is:"); 
  for (temp = head; temp != NULL; temp = temp->leaf)
  {
    printf ("Node @ %p has %d\n", (void*)temp, temp->i);
  }

  temp = FindLowestNodeParent(head);
 
  printf ("Lowest parent: @ %p with %d\n", (void*)temp, temp->i);
 
  for (temp = head; temp != NULL; )
  {
    head = temp;
    temp = temp->leaf;
    free(head);
  }
 
  return(0);
}

/*
 * Output
 
The list is:
Node @ 008428CC has 0
Node @ 008428DC has 1
Node @ 008428EC has 2
Node @ 008428FC has 3
Node @ 0084290C has 4
Node @ 0084291C has 5
Node @ 0084292C has 6
Node @ 0084293C has 7
Node @ 0084294C has 8
Node @ 0084295C has 9
Node @ 0084296C has 10
Lowest parent: @ 0084295C with 9
freeing 008428CC
freeing 008428DC
freeing 008428EC
freeing 008428FC
freeing 0084290C
freeing 0084291C
freeing 0084292C
freeing 0084293C
freeing 0084294C
freeing 0084295C
freeing 0084296C
*/

---

As you can see it isn't a tree, only a linked list, but the principles can still be applied. I'll leave it up to you to amend the code to suite your needs (or ignore me if you want ;) ) It'll also need amending for short lists. Oh heck, it needs amending loads for you... oh well, have fun. :)