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

What have you tried?

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.

Quote:

---

Originally Posted by laserlight

What have you tried?

---

Nothing.

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

Quote:

---

Originally Posted by foxman

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 ?

Quote:

---

Originally Posted by outlaw525

Nothing.

---

Well, then, we wish you the best of luck.

Well, get started. First step, you said it yourself:

Quote:

---

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

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.

Quote:

---

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.

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

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;
}

---

Quote:

---

Originally Posted by outlaw525

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.

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)

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.

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