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

This is a discussion on "Which parent has children with no children"?!? within the C Programming forums, part of the General Programming Boards category; Hello, I'm currently messing about (As usual), cooking up an octree (That's a tree containing nodes with up to 8 ...

  1. #1
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,259

    Red face "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!

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

  2. #2
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    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...

  3. #3
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    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.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 10-15-2008, 09:24 AM
  2. pipe
    By smart girl in forum C Programming
    Replies: 4
    Last Post: 04-30-2006, 09:17 AM
  3. forks and children
    By suigeneris in forum C Programming
    Replies: 1
    Last Post: 01-22-2005, 04:48 AM
  4. Scale MDI child to parent
    By bludstayne in forum C# Programming
    Replies: 0
    Last Post: 07-10-2004, 02:26 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21