[jayburn00]

I am making a program that uses a file for input, but later gives the option to add to the tree via user input. Thing is, from what I can tell, a tree is not the most effective structure to use to make a family tree ironically. The problem I am having is figuring out how one could make a spousal relationship. I have already come up with some possibilities, but none of them are "pretty" and all them involve adding massive amounts of extra code: one possibility is to make use of multiple trees, stored in a vector, with the spouse in one of the other trees, but by having the same descendants, the program automatically knows there is a spousal relationship. That is one way. Another way is if you could have a tree where the spouse from outside the family is connected to the children, basically being 1 family tree merged with another but with the root node being the spouse, but I don't know how I would implement this one though, and not the first one either, I don't know how to get the program to do a cross reference between trees stored in a vector. I know how to implement a vector and how to implement a simple binary tree, but that's it. Anyway, any ideas on how I would go about making something like this? Unfortunately it has to be tree(our teacher seems fond of using nonoptimal structures for certain problems, this is the second time where he required us to use a particular structure for an assignment when there were structures that were much more effective and useful for the problem).

[modi123_1]

I think you'll need a new structure other than a tree... like a tree++.

Redefine the nodes as not people but that can also be relationships..

Aka.. a node contains a relationship of people but not so much the person themselves..

[Skydiver]

If you fall back on graph theory, I think that tree is still the appropriate structure since there should not be any cycles: http://en.wikipedia...._(graph_theory) if you follow strict parent-child and spouse relationships. All best are off if the family practices incest.

This post has been edited by Skydiver: 16 July 2012 - 05:19 PM

[jayburn00]

What is a tree++? And I don't even understand the graph theory stuff. It has to be a binary search tree, but I don't know how you could get a spouse on something like that. It would look almost like the beginning of a seperate tree is the only thing I can think of. The teacher said in class that the spouse could be determined by descendants, which makes me think that he is talking about the vector of trees idea. But the assignment only talks about one binary search tree. On top of which, when I tried to split the code I have into a .h file for the class declarations, and a .cpp file for defining the member functions, it had a hissy fit. I think it is partly because it is a template that we are using instead of a normal class. But I don't think that would effect the ability to split class from implementation. When I tried to use a normal data type in place of the template name(obj), it had a hissy fit. When I used the template data definition (obj) it had a hissy fit. Here is the header file that I am using to create the tree:

#ifndef TREEOBJECTS_H
#define TREEOBJECTS_H
//simple class to represent a binary tree node
template <class Obj>
class Node 
{
public:
	Node(Obj data):left(NULL), right(NULL)
	{
		this->data = data;
	}

	Node(): left(NULL), right(NULL){} //default constructor

	Obj data;
	Node<Obj> *left, *right;
};

//class template of a simple BST
template<class Obj>
class BST
{
public:
	//default constructor
	BST()
	{
		this->size = 0;
		this->root = NULL;
	}

	//return the smallest element in the BST
	Obj findMin()
	{
		if( this->root != NULL)
		{
			Node<Obj> * p = this->root;

			while(p->left != NULL)
			{ //go to the left most
				p = p->left;
			}
			return p->data;
		}
		else
		{ //empty BST => throw exception
			cout<<"\nCan't access an empty BST\n";
			exit(0);
		}
	}

	//insert a node to the tree
	void insert(Obj data)
	{
		//create a node with the given data
		if(this->root == NULL) 
		{
		   this->root = new Node<Obj>(data);
		}
		else
		{
			insert(this->root, data);
		}
		this->size++; //increment the list count
	}
	 
	//insert a node given a pointer to a tree node
	void insert(Node<Obj> *node, Obj & data)
	{
		if(node != NULL)
		{
			if(node->data > data)
			{
				if(node->left != NULL)
				{
					insert(node->left, data); //insert to the left
				}
				else
				{
					node->left = new Node<Obj>(data);
				}
			}
			else if(node->data < data)
			{
				if(node->right != NULL)
				{
					insert(node->right, data); //insert to the right
				}
				else
				{
					node->right = new Node<Obj>(data);
				}
			}
			else
			{ //duplication
				this->size--;
			}
		}
	}
 
	//print all the elements starting with the root based on the given type
	// 0 = inorder, 1 = preorder, 2= post order
	void print(int type)
	{
		if(this->root != NULL)
		{
			switch(type)
			{
			case 0:
				printInOrder(this->root);
				break;
			case 1:
				printPreOrder(this->root);
				break;
			case 2:
				printPostOrder(this->root);
				break;
			}
		}
	}
	//print the tree inorder
	void printInOrder(Node<Obj> *node)
	{
		if( node != NULL)
		{
			printInOrder(node->left);
			cout<< " " << node->data;
			printInOrder(node->right);
		}
	}

	//print the tree pre-order
	void printPreOrder(Node<Obj> *node)
	{
		 // put implementation here
	}
	
	//print the tree pre-order
	void printPostOrder(Node<Obj> *node)
	{
		 // put implementation here
	}

	//delete the tree from a given root
	void deleteAll(Node<Obj> *node)
	{
		if(node == NULL)
			return;
		deleteAll(node->left);
		deleteAll(node->right);
		delete node;
	}

	//destructor
	~BST()
	{
		if(this->root != NULL)
		{
			deleteAll(this->root);
		}
	}

private:
	int size; // the number of nodes in the tree
	Node<Obj> *root; //root of the tree
};
#endif

Here is the cpp file that is going to be an .obj file when compiled:
#include "treeObjects.h"
#include <string>
#include <cstring>
#include <iomanip>
#include <iostream>

using namespace std;


int //What goes here?  ::BST::findMin

I have no idea what to do there. If I can figure out how to get just one of the member functions working in the implementation file, it will be great. However, that is only one of the problems. I don't see how it is possible to do that thing with the spouse in a Binary search tree, here is why:

spouse1------spouse2

|||||| |||||

Actually I don't even know how I am going to represent the thing here, so ignore above. The graph theory is unhelpful because it doesn't actually explain whether I can do something in C++ or not (such as having a root node to the side of the graph, which connects to a child, which is already connected to another parent which eventually connects to the main root node; I don't even think this would be a tree anymore actually would it?). Don't know. I asked the teacher but he was extremely unhelpful, just saying again that you look to see if the children have multiple parents which then indicates spouse. How?

[#define]

Templated classes etc do not have normal implementation files. Until the class is compiled the data type passed using the template is not known within the class or the functions. So the functions need to be available at compile time. They can added to the header file, in your case they are defined in the class.

The family tree programs I have come across have a list of persons with id numbers. Your person data could contain id's of spouses, parents and children.

Edit: I suppose each person has two parents!

Making Family Tree in C++

This post has been edited by #define: 16 July 2012 - 09:33 PM

[Skydiver]

Sorry, that link doesn't seem to go anywhere useful... It jumps to a thread where Martyr2 responded with his own link, but that link just goes to the DIC front page.

[Skydiver]

The only reason why I brought up the exact definition of a tree as is that it supposed to be a set of nodes connected to each other such that there is no cycle. And computer science tends to rely heavily on graph theory for compilers, path finding routines, etc. (Assuming no incest), a family tree where the vertices represent individuals, and the edges represent either parent-child relationships, or spouse relationships satisfies the definition of a tree.

I tend to agree with the OP. I'm just not seeing a way of using a just a binary tree to represent a family tree. If somebody can hint how it is possible, that would be great.

[jimblumberg]

Quote

But I don't think that would effect the ability to split class from implementation. When I tried to use a normal data type in place of the template name(obj), it had a hissy fit. When I used the template data definition (obj) it had a hissy fit. Here is the header file that I am using to create the tree:

In C++ when dealing with templates both the implementation and definition must be in the same compilation unit. Which usually means in the same file.

If you use a "family" as the search condition a tree seems to be applicable. Each "family" consists of the parents and all their children. These children can also be the root of their own "family".

Jim

[jayburn00]

jimblumberg actually has a good idea it sounds like, I think I heard about something similar from a fellow student. But I am still having trouble understanding the actual layout for the thing. Could someone post a picture or diagram? I learn visually so I have a bit of trouble understanding written explanations(I nearly always give directions to people in terms of landmarks instead of street names, and I prefer directions that way myself.) One of the issues I have with jimblumberg's idea though is that it seems there would be multiple roots. Also I found out from the teacher that there are two ways of doing the tree. One sounds the same as jimblumberg's idea, and the other is not even a binary tree(the teacher's directions imply the use of a binary tree, but apparently he did not mean to.

[Skydiver]

I think I partially answered my question about how to represent a family tree. It follows the pattern here: http://www.cs.ccsu.e...ones/chap17.pdf (see pp.17-3 and 17-4) where left child is a descendant, an that descendants right child represent the next siblings.

However that system still does not account for marriage relationships. It also only cares about paths back to your ancestors roots. It doesn't matters if you married a Kennedy, your kids are still children of an Estonian serf.

To complicate matters, how do you handle adoptions within an extended family? Do you move that sibling or keep them where they are?

Also how do you handle relatives that are distantly related because they know the primary root, but they don't know the intermediate generations?

So please, can somebody please describe how to use a binary tree to represent a family tree suitable for genealogy? I feel that the page that I linked to that ostensibly was using a binary tree for genealogy failed utterly.

[jimblumberg]

In a genealogy program you are actually tracking events, not necessarily individuals. A Family tree starts with the first relationship event, whether that is a marriage or the birth of their first descendant, thus creating a "family" event. Also there are different types of trees to consider. The most common being a descendant tree, where everything stems from the ultimate parents. The second most common is the ancestor tree that start from a single individual and finds all his/her ancestors.

Quote

However that system still does not account for marriage relationships.

It is possible for a person to have multiple wives or husbands, each marriage/relationship is an family type event. I do agree things can get complicated. For example my grandfather remarried after my grandmother died. The strange part about this is that he married my great aunt, the sister of his dead wife. Since this second wife also had children are these children your uncles/aunts or are they cousins? My father always considered her as his aunt, not a step mother, this may have been because this marriage lasted less than a year before my grandfather died and my father was already an adult at the time of this marriage. Also if this new marriage would have produced children where would they fit?

Quote

To complicate matters, how do you handle adoptions within an extended family?

Adoptions are considered a family event. The adopted child still retains his/her birth parents but now also gains the adopted parents.

Quote

Also how do you handle relatives that are distantly related because they know the primary root, but they don't know the intermediate generations?

There are several ways of dealing with this, one is to add placeholders for the missing generations. Then as your research reveals the missing information you modify these placeholders. The other method is that until you have the connecting information these individual families are separate and unrelated. As you fill in the gaps the separate "families" will merge at the proper point. The finding of this missing information is the key to creating your trees. I myself have this exact problem. I am aware of distant cousins but have not until recently been able to determine exactly how these separate families were actually connected. I was able to finally "connect the dots" because I found one of these cousins living with his grandparents and his grandparents were one of the "missing links". Before this I had been unable to determine their names, but with this new information I was able to link these two separate trees.

Jim

[jon.kiparsky]

jayburn00, on 16 July 2012 - 09:49 PM, said:

What is a tree++? And I don't even understand the graph theory stuff. It has to be a binary search tree, but I don't know how you could get a spouse on something like that.

Family trees are not binary, nor are they search trees.

They are not binary: Nodes in a binary tree may have at most two child nodes. No such restriction exists on a family, although I understand Chinese computer scientists are doing interesting research on the unary search tree.

They are not search trees: A binary search tree organizes linear information by sort order: you know whether to branch left or right by comparing your target to the current node - less means left. The information contained in a binary search tree is typically experienced in real life as a flat list, like a series of dictionary entries or contacts in a phone book.

A family tree represents an actual hierarchy, so it can't be a search tree, and there is no restriction on the number of descendents allowed to a particular node. Either you've misunderstood the assignment, or your professor has.

This post has been edited by jon.kiparsky: 18 July 2012 - 07:49 AM

[macosxnerd101]

You might be better off organizing it as a directed graph rather than approaching it as a tree. Yes, it will most likely still satisfy the definition of a tree, but a directed graph might be clearer to work with here. Especially if you are tracking your ancestry from both your mother's and father's sides. If you do that, you would be getting into multi-parented trees. In which case, a digraph is just cleaner.

[jayburn00]

Going back to C++, how does one even create a tree. I tried with my program above, I know it is missing that implementation part, I tried putting a couple of things there, but nothing I came up with worked. Doesn't help matters that I'm having a migraine. Also, here are some of the specs of the program:


Requirements: modify and complete the BST we have partially finished in the class accordingly and use it for the following program:
1. Load a data file: load file ancestry.dat with into your tree. The file has the following format:
parent(X,
parent(X,B,C)
parent(John Doe, Mary Jane)
child(B,X)
child(Joe, Mary Jane)
child(B,X,Y)
male(X)
female(Y)
….
This is how to interpret the data
+ parent(X, means X is the parent of B; parent(X,B,C) means X has two children B and C. Assume there is no more than two children
+ child(B,X) and child(B,X,Y) mean B is a child of X and B is a child of Y
+ All data are case-insensitive.
+ Do not store duplicate nodes
2. Your program should the provide the user with the following options
a. Print the tree in level-order from root to leaves (hint: a stack can help)
b. Add new entry – the given entry will be in the same format as the file
c. Confirm
d. Search for children, ancestors, descendants, or siblings from any node (obtain the node data from the user)
e. Exit – asks user whether if they want to save the tree back to the file or not – then acts accordingly.
The “confirm” option, worth 50 points, will take in a relation and answer true or false. The following relations must be implemented: ancestor(X,Y), decedent(X,Y), wife(X,Y), and husband(X,Y).

I think the Parent(X,Y) could be read as a function. However, I have never made a function that passed more than one parameter before (actually I probably have done 1 where it passed 2, but very long ago and can't remember how). I think also that the functions could somehow do inserts into the tree. Oh, and operate on the assumption that it is not a binary search tree despite what the assignment says. How can one simply a general tree that one is able to run a comparison of children and parents of each node? Ignore the smiley faces, those are supposed to be parentheses and something else.

This post has been edited by jayburn00: 18 July 2012 - 12:44 PM

[macosxnerd101]

Do you know how to create a Linked List? It's the same general principle, except each Node has n children Nodes instead of one next Node.