Thread: Question: Binary Tree only with parent pointer

  1. #1
    Registered User
    Join Date
    Jun 2008
    Posts
    7

    Question: Binary Tree only with parent pointer

    Hi,

    The fuction should work in C.

    I need to create a struct for tree with pointer to parent only, without pointers to left & right childs.

    The function got two pointers for two childs and printer the shared parent of them.

    The function will print the info of the shared parent.

    I attached a doc file that show what I want, there is two blue childs that the red parent is the one that the function need to print.

    I alse need to know the struct elements.

    Sorry for my english.

    Thanks alot

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    What have you tried?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    This looks like a "funny" way to implement a tree. But I wouldn't call this a tree, since it lose quite a lot (if not all ?) of it's interesting properties. But this is another story.
    I hate real numbers.

  4. #4
    Registered User
    Join Date
    Jun 2008
    Posts
    7
    Quote Originally Posted by laserlight View Post
    What have you tried?
    Nothing.

    I need a solution for that. it's for my study.

  5. #5
    Registered User
    Join Date
    Jun 2008
    Posts
    7
    Quote Originally Posted by foxman View Post
    This looks like a "funny" way to implement a tree. But I wouldn't call this a tree, since it lose quite a lot (if not all ?) of it's interesting properties. But this is another story.
    So, can you help me with that ?

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by outlaw525 View Post
    Nothing.
    Well, then, we wish you the best of luck.

  7. #7
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Well, get started. First step, you said it yourself:
    I need to create a struct for tree with pointer to parent only, without pointers to left & right childs.
    In code:
    Code:
    struct tree {
        struct tree *parent;
    };
    That wasn't too hard, was it? . . . .

    Now you'll probably need to allocate the structures as you have done in your diagram, just so you can test the function you're going to write.

    The function [takes] two pointers for two childs and [prints] the shared parent of them.
    That's a little big harder. One way of doing this that comes to mind is to examine all of the parents of one child until you reach the top of the tree, checking to see if you find one that equals the other child. If not, start comparing with the parent of the other child instead, and so on until you find what you're looking for.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  8. #8
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    Quote Originally Posted by dwks
    Code:
    struct tree {
        struct tree *parent;
    };
    I wouldn't call this struct a "tree" since it can only result in a linked list at best. We should definitely call this a "node" in this case. But I'm being pedantic.

    I guess the "tree" struct would contains a list of "leafs". Maybe something like
    Code:
    struct tree
    {
       struct node **leafs;    // Array of leafs
       size_t nbLeafs;
    }
    I hate real numbers.

  9. #9
    Registered User
    Join Date
    Dec 2007
    Posts
    2,675
    Quote Originally Posted by outlaw525 View Post
    Nothing.

    I need a solution for that. it's for my study.
    Nice effort you're showing there.

    Do us all a favor, will you? Choose a different career path.

    Kthxbye.

  10. #10
    Registered User
    Join Date
    Jun 2008
    Posts
    7

    Question Please check my function

    I wrote the following function, please tell me if she is ok.
    Code:
    struct node{
            int info;
            struct node * parent;
    };
    
    typedef struct node node;
    
    
    void sameParent (node * n1, node * n2)
    	{
    	node * save_n2 = n2;
    	while (n1 != NULL)
    		{
    		n2=save_n2;
    		while(n2 != NULL)
    			{
    			if (n1 == n2)
    				{			
    				printf ("%d",n1->info);
    				return;
    				}
    			else
    				n2=n2->parent;
    			}
    		n1=n1->parent;
    		}
    	printf ("No shared parent");
    	}
    1) The function should print the share parent or "No shared parent" when is'nt exist.

    2) Can someone offer more effective code ? this one is O (n^2)
    Last edited by outlaw525; 06-23-2008 at 04:53 PM.

  11. #11
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    It looks like that would work. I'd probably write it differently, of course. It's the kind of thing that lends itself to for loops. But I can't think of a better algorithm at the moment. (Unless you want to use a lot of memory and record every parent or something like that.)

    That might work, actually. Record the parents of one "leaf", keeping the list of parents sorted by using an insertion sort of some kind. Then, going through the parents of the other leaf, do a binary search on the parents of the other leaf, checking for matches.

    That's basically using a binary search instead of a linear search. It involves a lot of overhead, though, and would probably only be faster for very large "trees" . . . .

    BTW: It's always a good idea to print a newline after your messages.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  12. #12
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    [code]
    It's the kind of thing that lends itself to for loops.
    [/quote]

    Personally I find trees and linked lists more suited to while loops. For's are just ugly for this.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Question About Pointer To Pointer
    By BlitzPackage in forum C++ Programming
    Replies: 2
    Last Post: 09-19-2005, 10:19 PM
  2. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  3. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 10:18 AM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. Templated Binary Tree... dear god...
    By Nakeerb in forum C++ Programming
    Replies: 15
    Last Post: 01-17-2003, 02:24 AM