[jayburn00]

Also, if someone could just create an example code for a tree of say maybe 5 family nodes, with parents, childs, etc etc, would appreciate that as well. Another thought also occured to me regarding the issue of the dummy parent may end up having more than 2 children: If there ends up a situation where the dummy parent is going to have more than 2 children, than a new dummy parent is created as a child of the dummy parent, always maintaining the parent having no more than 2 children, even for the dummy parent. Here is how it works: gah, never mind, first let me ask, can a tree have branches that come back together at a child node?
Kind of like 2 v's, one upside down and put together? I don't think its a tree anymore then. But I don't know. Because if a dummy parent is used, I think you would end up with such an organization. What about the dummy child idea? grrr... this project is driving me cuckoo for cocoa puffs. I need to do it though, even if it is impossible. I am starting to think that I could get away with something that resembled a tree but wasn't strictly a tree. Any suggestions? Preferably one where I stay with tree since that is what is in this abomination of an assignment, but at the moment, I am unable to come up with a tree that is able to do the stuff needed. Unless its possible to have a spouse node that has no parent, or a node that has no parent but is not the main root node. If that is possible, that would cure a lot of headaches.

[jayburn00]

In my data structures book I found an example code for traversing a tree in level order, but it seems to be missing context (the book is very bad at that, gives stuff without any context to use it in). Because of the missing context, the book just gave me a piece of code that doesn't work without whatever is missing. There are two files it appears, but both start with Template <class Object> and neither appears to be main file or has any include statements. If you have any insight into what is missing feel free to tell me. Here is the first part, I haven't typed the second part yet. The only thing missing is a few comments and the second file which I will post later:

template <class Object>
class LevelOrder : public TreeIterator<Object>
{
public:
	LevelOrder( const BinaryTree<Object & theTree);
	~LevelOrder() { }

	void first();
	void advance();
private:
	Queue< const BinaryNode<Object> * >q;
};

template <class Object>
LevelOrder<Object>::LevelOrder( const BinaryTree<Object> &
	theTree ) : TreeIterator<Object>( theTree )
{
	q.enqueue( root );
}

[Skydiver]

jayburn00, on 20 July 2012 - 06:38 PM, said:

Ok, I just ran into one snag with the btree idea. It won't work with the dummy parent, because you won't know how many children of the dummy parent there are later. Remember this program will be use any variant on the input spoken above, including user input.

I thought that was pretty obvious even with the binary tree that if you go with the dummy parent idea, you'd be forced to have multiple dummy parents. All the B-tree does delay creating the dummy parents.

So let's say you had a B-tree that supports 3 children that looks like:

  Dummy0
 /  |  \
P1  P2  P3
|   |   |
C1  C2  C3

as a result of

child(C1, P1)
parent(P2, C2)
child(C3, P3)

When you got the next input of child(C4, P4), what needed to happen was:

         Dummy2
        /  |
  Dummy0   Dummy1
 /  |     /  |
P1  P2   P3  P4
|   |    |   |
C1  C2   C3  C4

This post has been edited by Skydiver: 22 July 2012 - 02:36 PM

[Skydiver]

jayburn00, on 20 July 2012 - 06:38 PM, said:

If someone could take the time to explain any line where a period is used, a back slash, any number of colons, asterisks, or ->, I would appreciate that as well.

I think that you are in deep doo-doo if you are trying to tackle a data structures problem, but you are still trying to learn the language at the same time.

If the objective of the class is just to learn data structures, and if you know another programming language well, I highly recommend completing the assignment using that other language.

If on the other hand, the objective of the class is to learn data structures in C++, you will do well to review the first few chapters of your C++ book otherwise you'll not only be fighting an uphill battle understanding your teacher's accent, his use of the English language, but you'll also be fighting to learn C++ pointers, member variables, and escape characters in strings, on top of how to use C++ to implement data structures.

[jayburn00]

Skydiver, on 22 July 2012 - 02:34 PM, said:

jayburn00, on 20 July 2012 - 06:38 PM, said:

Ok, I just ran into one snag with the btree idea. It won't work with the dummy parent, because you won't know how many children of the dummy parent there are later. Remember this program will be use any variant on the input spoken above, including user input.

I thought that was pretty obvious even with the binary tree that if you go with the dummy parent idea, you'd be forced to have multiple dummy parents. All the B-tree does delay creating the dummy parents.

So let's say you had a B-tree that supports 3 children that looks like:

  Dummy0
 /  |  \
P1  P2  P3
|   |   |
C1  C2  C3

as a result of

child(C1, P1)
parent(P2, C2)
child(C3, P3)

When you got the next input of child(C4, P4), what needed to happen was:

         Dummy2
        /  |
  Dummy0   Dummy1
 /  |     /  |
P1  P2   P3  P4
|   |    |   |
C1  C2   C3  C4

Are you saying that for each parent without their own parent I would have to create a new dummy parent? That wouldn't be 'too' difficult. Be annoying, but means it is still possible. But what about there being 2 parents for child?

This post has been edited by jayburn00: 22 July 2012 - 03:40 PM

[Skydiver]

jayburn00, on 21 July 2012 - 03:13 PM, said:

There are two files it appears, but both start with Template <class Object> and neither appears to be main file or has any include statements. If you have any insight into what is missing feel free to tell me. Here is the first part, I haven't typed the second part yet. The only thing missing is a few comments and the second file which I will post later:

I don't think you need to type it in if the file you are thinking about are:
Iterate.h: http://www.cs.fiu.ed.../code/Iterate.h
Iterate.cpp: http://www.cs.fiu.ed...ode/Iterate.cpp

Found here: http://users.cis.fiu.../adspc++2/code/

[jayburn00]

Skydiver, on 22 July 2012 - 03:24 PM, said:

jayburn00, on 20 July 2012 - 06:38 PM, said:

If someone could take the time to explain any line where a period is used, a back slash, any number of colons, asterisks, or ->, I would appreciate that as well.

I think that you are in deep doo-doo if you are trying to tackle a data structures problem, but you are still trying to learn the language at the same time.

If the objective of the class is just to learn data structures, and if you know another programming language well, I highly recommend completing the assignment using that other language.

If on the other hand, the objective of the class is to learn data structures in C++, you will do well to review the first few chapters of your C++ book otherwise you'll not only be fighting an uphill battle understanding your teacher's accent, his use of the English language, but you'll also be fighting to learn C++ pointers, member variables, and escape characters in strings, on top of how to use C++ to implement data structures.

Previously I have taken 4 different courses on C++. Two were course called C++ 1 and C++ 2 as part of my associates degree in programming. We use C++ in Computer Science 1 and Computer Science 2. Unfortunately, for compsci 2, we had no teacher for 3 weeks and only had a minimal amount of assignments assigned online during this time. Took compsci 2 more than a year ago, the others even earlier. Everyone else in my Data Structures class had CS2 with a different person and did not have a missing 3 week gap.

Skydiver, on 22 July 2012 - 03:41 PM, said:

jayburn00, on 21 July 2012 - 03:13 PM, said:

There are two files it appears, but both start with Template <class Object> and neither appears to be main file or has any include statements. If you have any insight into what is missing feel free to tell me. Here is the first part, I haven't typed the second part yet. The only thing missing is a few comments and the second file which I will post later:

I don't think you need to type it in if the file you are thinking about are:
Iterate.h: http://www.cs.fiu.ed.../code/Iterate.h
Iterate.cpp: http://www.cs.fiu.ed...ode/Iterate.cpp

Found here: http://users.cis.fiu.../adspc++2/code/

Wow, that makes a lot more sense than the stuff in the book. The book just throws it on a page saying this puts it in such and such order. Would this work for trees other than BST or binarytree, whichever it was made for?

[Skydiver]

jayburn00, on 21 July 2012 - 12:15 PM, said:

first let me ask, can a tree have branches that come back together at a child node?
Kind of like 2 v's, one upside down and put together? I don't think its a tree anymore then. But I don't know.

People with more formal and rigorous training in graph theory, please correct me since I barely passed the course, but I believe that the following graph is considered a tree as long as the edge B->D and C->D are one directional. If they are bidirectional, then a cycle exists and it is not a tree anymore.

  ->A<-
 /     \
v       v
B       C
 \     /
  ->D<-

[Skydiver]

jayburn00, on 22 July 2012 - 03:38 PM, said:

Are you saying that for each parent without their own parent I would have to create a new dummy parent? That wouldn't be 'too' difficult. Be annoying, but means it is still possible.

No. Just follow the the standard rules for inserting into a binary or B tree. Only create new dummy parents when all the dummy parents are full.

jayburn00, on 22 July 2012 - 03:38 PM, said:

But what about there being 2 parents for child?

Since children only reference real parents, it doesn't matter.

jayburn00, on 22 July 2012 - 03:47 PM, said:

Wow, that makes a lot more sense than the stuff in the book. The book just throws it on a page saying this puts it in such and such order. Would this work for trees other than BST or binarytree, whichever it was made for?

What you need to take away from that is the concepts implemented by the code, not the code itself. Take time to understand how the traversal algorithm works so that you can implement it on your own.

[jayburn00]

Skydiver, on 22 July 2012 - 03:49 PM, said:

jayburn00, on 21 July 2012 - 12:15 PM, said:

first let me ask, can a tree have branches that come back together at a child node?
Kind of like 2 v's, one upside down and put together? I don't think its a tree anymore then. But I don't know.

People with more formal and rigorous training in graph theory, please correct me since I barely passed the course, but I believe that the following graph is considered a tree as long as the edge B->D and C->D are one directional. If they are bidirectional, then a cycle exists and it is not a tree anymore.

  ->A<-
 /     \
v       v
B       C
 \     /
  ->D<-

Does that mean B and C can only have one child in that setup? I had another thought by the way. Is it possible to merge a small tree into the larger one like this:

P1
     /  \
     c1  c2

  P2 Ancestors
     |
     P2---     P1  
      \   \   / |
       \   c2   |
        \       |
         \     /
        c1-----

[Skydiver]

jayburn00, on 22 July 2012 - 04:10 PM, said:

Skydiver, on 22 July 2012 - 03:49 PM, said:

jayburn00, on 21 July 2012 - 12:15 PM, said:

first let me ask, can a tree have branches that come back together at a child node?
Kind of like 2 v's, one upside down and put together? I don't think its a tree anymore then. But I don't know.

People with more formal and rigorous training in graph theory, please correct me since I barely passed the course, but I believe that the following graph is considered a tree as long as the edge B->D and C->D are one directional. If they are bidirectional, then a cycle exists and it is not a tree anymore.

  ->A<-
 /     \
v       v
B       C
 \     /
  ->D<-

Does that mean B and C can only have one child in that setup?

They can have more than one child. (Assume all edges are one direction from parent to child.)

    A
   / \
  /   \
 B     C 
/ \   / \
\  \ /   \
 \  D     \
  \_______|
          E

jayburn00, on 22 July 2012 - 04:10 PM, said:

I had another thought by the way. Is it possible to merge a small tree into the larger one like this:

P1
     /  \
     c1  c2

  P2 Ancestors
     |
     P2---     P1  
      \   \   / |
       \   c2   |
        \       |
         \     /
        c1-----

Sort of...

If all the lines are bi-directional, then you can do a merge, but result you get is not a tree because you now have a cycle.

If all the line are uni-directional from parent to child, P1 is sort of in limbo. Yes, P1 points to C1 and C2, but C1 and C2 can't get back up to the parent because they don't have pointers to their parents.

Unfortunately, the only way to make the spouse() relationship check work is by having pointers back up to the parents, which then allows for a cycle which then makes the graph not a tree.

[Skydiver]

I have finally resolved in my mind the conflict caused by "that's not a tree if it has a cycle" and "but you need the upward child->parent link to determine spouse() relationship".

If I were to implement things, there is one Graph that contains all the nodes. I will not use a tree. With in the Graph, there are "parent->child" trees and "child->parent" trees that connect the nodes. For the sake of lookup, there is also an external binary search tree so that a node with a given name can be found quickly. (Alternately a linear search through a list of all nodes can also be done. It'll be cheaper than trying to walk the graph looking for a matching node.) There is no need for dummy parents. They just complicate things with all the special cases.* Instead there is a list of nodes without parents which will be used as starting points for level 0 to satisfy 2.a.

*Funny how this statement is also sometimes amusingly true in real life: "There is no need for dummy parents. They just complicate things with all the special cases."

[jayburn00]

Skydiver, on 22 July 2012 - 10:04 PM, said:

I have finally resolved in my mind the conflict caused by "that's not a tree if it has a cycle" and "but you need the upward child->parent link to determine spouse() relationship".

If I were to implement things, there is one Graph that contains all the nodes. I will not use a tree. With in the Graph, there are "parent->child" trees and "child->parent" trees that connect the nodes. For the sake of lookup, there is also an external binary search tree so that a node with a given name can be found quickly. (Alternately a linear search through a list of all nodes can also be done. It'll be cheaper than trying to walk the graph looking for a matching node.) There is no need for dummy parents. They just complicate things with all the special cases.* Instead there is a list of nodes without parents which will be used as starting points for level 0 to satisfy 2.a.

*Funny how this statement is also sometimes amusingly true in real life: "There is no need for dummy parents. They just complicate things with all the special cases."

Sorry don't understand that. And I really don't have an option of not doing a tree.

P1      P2
      |  \   / |
      |   \ /  |
      |   / \  |
      C1     C2

That is a diagram of the parent child relationship in the tree. So the tree would be made up of a bunch of these units, with the root at the top. So how do I implement that. I am now out of time, assignment is due tommorrow and I don't have anything to turn in

[jayburn00]

Ok, just talked with my teacher and I have decided that having the last generation be the root works better than having an ancestor as a root (not to mention, a lot of real family trees work this way. Now, I know how to fill a tree with predefined nodes, but how do you create them using the information from a data file such that Child(George, Martha, Henry) means that George is the child of Martha and Henry? And that Child(George, Martha, Henry) creates three different nodes in the tree. It looks like constructing a tree and then filling it won't work, because we don't know which nodes will be filled and which will have nothing in it. It needs to be assembled from the data given. Ignore my earlier statement of out of time by the way, I still have 24 hours. Also, this means that the current generation will have only one child represented in it. Every child has 2 parents, so that means a relatively simple tree will suffice (barring remarrying. Keep it simple, so assume that everyone stays married to the same person. So how exactly would I create a function to do this.

This post has been edited by jayburn00: 23 July 2012 - 11:11 AM

[Skydiver]

If you decide to make the last generation the root the handling Child(George, Martha, Henry) should build a tree like this:

       George
      /      \
Martha        Henry

And the pseudo code for it would look like:

parse input "op(x, y, z)" into opName, childName, parentName1, parentName2
if opName == "Child" && parentName != "" && parentName2 != ""
{
    childNode = LookupNode(childName);
    if (null == childNode)
    {
        childNode = new Node(childName);
        root = childNode;
    }
    childNode->Left = LookUpOrCreate(parentName1);
    childNode->Right = LookUpOrCreate(parentName2);
}

Node * LookUpOrCreate(name)
{
    Node * node = LookupNode(name);
    if (node == nullptr)
        node = new Node(name);
    return node;
}

Node * LookupNode(name)
{
    FindNodeRecursively(root, name);
}

Node * FindNodeRecursively(node, name)
{
    if (node == nullptr)
        return nullptr;
    if (node->Name == name)
        return node;
    Node * parent = FindNodeRecursively(node->Left, name);
    if (parent == nullptr)
        parent = FindNodeRecursively(node->Right, name);
    return parent;
}

I'm still not convinced that having the latest generation at the root works because how do you deal with an empty tree and then get:
Child(George, Martha, Henry)
Child(Thomas, Martha, Henry)

You can't have binary tree with two roots.

This post has been edited by Skydiver: 23 July 2012 - 06:57 PM