# Search and Build Tree

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 11-13-2002
1999grandamse
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!
• 11-13-2002
1999grandamse
or does anyone have a sample program on Family Trees
• 11-13-2002
kermi3
Do you have anything so far that does work? What is your problem? just the algorithum to locate and insert or the code itself? If it's the code what part don't you get?
• 11-13-2002
1999grandamse
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.
• 11-13-2002
kermi3
Define Family tree.

What is the part that's giving you trouble? Is it something the tree has to have that a binary doesn't?
• 11-13-2002
1999grandamse
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...
• 11-13-2002
kermi3
I know, I'm trying to get you to come up with the answer...I have one I think will work, but my just giving it to you won't help, if you figure it out you'll understand it a lot better....

What is the diffrence in a binary tree and the one you need? Just list the diffrences and why you can't do them.
• 11-13-2002
PJYelton
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.
• 11-13-2002
1999grandamse
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?
• 11-13-2002
kermi3
What is the diffrence in a binary tree and the one you need? Just list the diffrences and why you can't do them. List them.
• 11-13-2002
PJYelton
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.
• 11-13-2002
1999grandamse
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.
• 11-13-2002
1999grandamse
i can post the class i have available to me if that would make it easier for you...
• 11-13-2002
kermi3
yeah do that please. do you have to use this class or did you make it up?
• 11-13-2002
1999grandamse
// 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> * was;

was = where.current;
add = new Tnode<Etype>(one); // Create node with data
if (was != NULL) // Fill in pointers
{
}
else // Special case for making the root
{
}
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> * 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
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
}
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last