Search and Build Tree

This is a discussion on Search and Build Tree within the C++ Programming forums, part of the General Programming Boards category; I am working on a program in which I build a Family Tree. In order to build the tree, I ...

  1. #1
    Registered User
    Join Date
    Sep 2002
    Posts
    64

    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!

  2. #2
    Registered User
    Join Date
    Sep 2002
    Posts
    64
    or does anyone have a sample program on Family Trees

  3. #3
    Lead Moderator kermi3's Avatar
    Join Date
    Aug 1998
    Posts
    2,595
    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?
    Kermi3

    If you're new to the boards, welcome and reading this will help you get started.
    Information on code tags may be found here

    - Sandlot is the highest form of sport.

  4. #4
    Registered User
    Join Date
    Sep 2002
    Posts
    64
    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.

  5. #5
    Lead Moderator kermi3's Avatar
    Join Date
    Aug 1998
    Posts
    2,595
    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?
    Kermi3

    If you're new to the boards, welcome and reading this will help you get started.
    Information on code tags may be found here

    - Sandlot is the highest form of sport.

  6. #6
    Registered User
    Join Date
    Sep 2002
    Posts
    64
    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...

  7. #7
    Lead Moderator kermi3's Avatar
    Join Date
    Aug 1998
    Posts
    2,595
    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.
    Kermi3

    If you're new to the boards, welcome and reading this will help you get started.
    Information on code tags may be found here

    - Sandlot is the highest form of sport.

  8. #8
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  9. #9
    Registered User
    Join Date
    Sep 2002
    Posts
    64
    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?

  10. #10
    Lead Moderator kermi3's Avatar
    Join Date
    Aug 1998
    Posts
    2,595
    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.
    Kermi3

    If you're new to the boards, welcome and reading this will help you get started.
    Information on code tags may be found here

    - Sandlot is the highest form of sport.

  11. #11
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  12. #12
    Registered User
    Join Date
    Sep 2002
    Posts
    64
    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.

  13. #13
    Registered User
    Join Date
    Sep 2002
    Posts
    64
    i can post the class i have available to me if that would make it easier for you...

  14. #14
    Lead Moderator kermi3's Avatar
    Join Date
    Aug 1998
    Posts
    2,595
    yeah do that please. do you have to use this class or did you make it up?
    Kermi3

    If you're new to the boards, welcome and reading this will help you get started.
    Information on code tags may be found here

    - Sandlot is the highest form of sport.

  15. #15
    Registered User
    Join Date
    Sep 2002
    Posts
    64
    // 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
    }

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Opinions on custom system build
    By lightatdawn in forum Tech Board
    Replies: 2
    Last Post: 10-18-2005, 05:15 AM
  2. Building B-Tree from Arrays
    By 0rion in forum C Programming
    Replies: 1
    Last Post: 04-09-2005, 03:34 AM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Building a Binary Search Tree off sorted data
    By BlackCitan in forum C Programming
    Replies: 0
    Last Post: 12-01-2003, 09:52 PM
  5. using traversal pairs to build a tree
    By Unregistered in forum C++ Programming
    Replies: 0
    Last Post: 05-07-2002, 12:51 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21