Thread: Search and Build Tree

I am working on a program in which I build a Family Tree.
In order to build the tree, I have to search the tree to see if the name exists and then insert.

I tried to do this type of search, but I found out it only worked on binary search trees:

while (iteratorFirst != myFTree.end() && *iteratorFirst != firstBorn)
{
if(firstBorn < *iteratorFirst)
iteratorFirst = iteratorFirst.DownFirst();
else
iteratorFirst = iteratorFirst.DownSibling();
}
myFTree.insertL(iteratorFirst, firstBorn);

Like I said, this doesn't work. Could someone help me please with a LOCATE and INSERT function to build my tree.

Thanks!

or does anyone have a sample program on Family Trees

no, its that i don't know the code. i know the code for a binary search tree, but not just a regular family tree. i want to search my family tree, and then insert. i can do the insert, but i don't know how to set up the search of the tree. that is what i need help with.

think of a family tree...

example, your grandparents have 4 kids, and those kids (your parents) could have one kid, two kids, three kids, etc or no kids. its just like you would think a family tree is. so the tree has to have a traversal and then insert depending on whose kid it is.

what i'm looking for is a general search of a tree. that is all i need...

For the search part, are you able to do a recursive function that searches the entire tree? It could start at the top, loop through each of the children while calling itself to be performed on each of the children, returning true when the name is found, or false if all of the children have been checked through the loop. Something like:

Code:

bool findName(node)
{
  if nodename=searchname return true
  else 
     for (x=1; x<(# of children); x++) {
          if (findName(child[x])) return true

  return false
}

Just pseudocode and needs a few more details like reporting back WHERE the name was found, but you should get the idea.

thank you, that does help somewhat....

the function i'm trying to get returns an iterator so i know where to insert.

any other ideas?

Maybe instead of returning a bool value, it can return an iterator. Instead of false it returns NULL, and instead of true it returns the spot to insert. Keep searching as long as the iterator is NULL. Just an idea, not sure if thats what you were looking for.

the tree i am working with can have multiple children while a binary tree can only have 2. however, i don't know how many children each node has prior to searching.

i can post the class i have available to me if that would make it easier for you...

// Node form for the family tree

template <typename Etype>
class Tnode
{
public:
Etype info; // The data
Tnode<Etype> *firstchild; // Points to first child (left)
Tnode<Etype> *sibling; // Points to a sibling (right)
Tnode<Etype> *parents; // Points to the parents (up)

Tnode () : firstchild(NULL), sibling(NULL), parents(NULL)
{ }
Tnode (const Etype & one) :
info(one), firstchild(NULL), sibling(NULL), parents(NULL)
{ }
};

// Template class for a family tree

template <typename Etype>
class FTree
{
private:
Tnode<Etype> *root; // Pointer to root node

void VisitAndDestroy(Tnode<Etype> *); // To erase subtree
FTree(const FTree &); // Make copy constructor
public: // inaccessible
class iterator;
FTree(); // Create empty tree
FTree (const Etype &); // Make single node tree
~FTree (); // Destroy tree
bool empty () const; // Test for empty
iterator begin() const; // Set iterator to root
iterator end() const; // Make iterator invalid
iterator insertL(iterator &, Etype &); // Add firstchild node
iterator insertR(iterator &, Etype &); // Add sibling node
void erase (iterator &); // Erase descendants


class iterator // Nested iterator
{
private:
Tnode<Etype> * current; // Pointer to tree node

iterator (Tnode<Etype> * where) // Make iterator point to a node
{
current = where;
}
public:
friend class FTree<Etype>; // Set relationship to tree
// Make iterator for client
iterator(): current(NULL)
{ };
// Compare iterators for =
bool operator == (iterator & rhs)
{
return current == rhs.current;
}
// Compare iterators for !=
bool operator != (iterator & rhs)
{
return current != rhs.current;
}
// Return reference to the
Etype & operator* () // data in the node
{
if (current == NULL)
throw logic_error ("Invalid dereference: *");
return current->info;
}
// Return pointer to the
Etype * operator-> () // data in the node
{
if (current == NULL)
throw logic_error ("Invalid dereference: ->");
return &(current->info);
}
// Return iterator referencing
iterator DownFirst () // firstchild node
{
if (current == NULL)
throw logic_error ("Invalid dereference: DownFirst");
return iterator(current->firstchild);
}
// Return iterator referencing
iterator DownSibling () // next sibling node
{
if (current == NULL)
throw logic_error ("Invalid dereference: DownSibling");
return iterator(current->sibling);
}
// Return iterator referencing
iterator Up () // parents node
{
if (current == NULL)
throw logic_error ("Invalid dereference: Up");
return iterator(current->parents);
}
};
};

// Recursive function to visit all nodes in subtree rooted
// at start and delete each node

template <typename Etype>
void FTree<Etype>::VisitAndDestroy(Tnode<Etype> *start)
{
if (start == NULL) return;
else {
VisitAndDestroy (start->firstchild);
VisitAndDestroy (start->sibling);
delete start;
}
}
// Build empty tree
template <typename Etype>
FTree<Etype>::FTree (void)
{
root = NULL;
}
// Build tree with root only
template <typename Etype>
FTree<Etype>::FTree (const Etype & one)
{
root = new Tnode<Etype>(one);
}
// Destroy whole tree
template <typename Etype>
FTree<Etype>::~FTree (void)
{
VisitAndDestroy (root);
root = NULL;
}
// Test for empty tree
template <typename Etype>
bool FTree<Etype>::empty () const
{
return root == NULL;
}
// Return iterator pointing to root
template <typename Etype>
FTree<Etype>::iterator FTree<Etype>::begin () const
{
return FTree<Etype>::iterator(root);
}
// Return iterator referencing NULL
template <typename Etype>
FTree<Etype>::iterator FTree<Etype>::end () const
{
return FTree<Etype>::iterator();
}
// Insert left child (firstchild) node
template <typename Etype>
FTree<Etype>::iterator FTree<Etype>::insertL // Return iterator ref new node
(FTree<Etype>::iterator & where, // Iterator to parent
Etype & one) // Data
{
Tnode<Etype> * add;
Tnode<Etype> * was;

was = where.current;
add = new Tnode<Etype>(one); // Create node with data
if (was != NULL) // Fill in pointers
{
add->firstchild = was->firstchild;
add->parents = was;
was->firstchild = add;
}
else // Special case for making the root
{
add->firstchild = add->sibling = add->parents = NULL;
root = add;
}
return FTree<Etype>::iterator(add); // Return iterator to new node
}
// Insert right child (sibling) node
template <typename Etype>
FTree<Etype>::iterator FTree<Etype>::insertR // Return iterator ref new node
(FTree<Etype>::iterator & where, // Iterator to parent node
Etype & one) // Data to add
{
Tnode<Etype> * add;
Tnode<Etype> * was;

was = where.current;
if (was == NULL)
throw logic_error ("Can't attach to an invalid iterator position");
add = new Tnode<Etype>(one); // Make new node with data
add->sibling = was->sibling; // Fill in pointers
add->parents = was->parents;
was->sibling = add;
return FTree<Etype>::iterator(add); // Return iterator to new node
}
// Erase descendants from start
template <typename Etype>
void FTree<Etype>::erase (FTree<Etype>::iterator & start)
{
Tnode<Etype> * other;

if (start.current == NULL) // Make sure start is valid
throw logic_error ("Can't erase; tree is empty or iterator invalid");
other = start.current->parents; // Locate parents
if (other != NULL)
{
if (start.current == other->firstchild) // If start if first child
other->firstchild = start.current->sibling; // Disconnect it
else
{
other = other->firstchild;
while (other->sibling != start.current) // Find which sibling start is
other = other->sibling;
other->sibling = start.current->sibling;// Disconnect it
}
start.current->sibling = NULL;
}
VisitAndDestroy(start.current); // Clear subtree
start = FTree<Etype>::iterator(); // Invalidate iterator
}