Thread: TreeNodes for more than two children

  1. #1
    Registered User
    Join Date
    Aug 2009
    Posts
    2

    TreeNodes for more than two children

    I'm a new member here and yes, my question is a homework question, but no i don't want a definite answer or for someone to do the entire homework for me. What I would like to know is if I'm heading in the right direction in solving this problem of mine. I like to solve the problems on my own but i've been trying to solve this to the point when I'm not entirely sure if I'm even heading in the right direction in solving it. Also the fact that the program won't compile, it keeps mentioning a "collect2: ld returned 1 exit status" error.

    The first part of the problem I worked out, which is having a TreeNode type class that basically maps a tree with no more than two children per node. The second part of the problem is trying to modify the code (that only allows two children per node) so that it allows more than two children. This is my code so far, I just want to know if I'm doing it right or completely wrong. at least if I know i'm wrong then I can try another way of solving it.

    The code is here:

    Header File
    Code:
    #ifndef TREENODE_H
    #define TREENODE_H
    
    #include <String>
    #include <list>
    
    using namespace std;
    
    class TreeNode
    {
            private:
                    char label;
                    list<TreeNode*> children;
    
            public:
                    TreeNode(char label);
                    ~TreeNode();
                    void setChildren(TreeNode* child); //in place of setLeft() and setRight()
    
                    void depthFirstTraversal();
                    void iterativeDeepeningSearch();
    };
    
    #endif // TREENODE_H
    Source File
    Code:
    #include <cstdlib>
    #include <iostream>
    #include "TreeNode.h"
    
    using namespace std;
    
    TreeNode::TreeNode(char label)
    {
        this->label = label;
        children.clear(); // equivalent to 'left = NULL' and 'right = NULL'
    }
    
    TreeNode::~TreeNode()
    {
        if(children.empty())
        {
            children.~list<TreeNode*>();
        }
    }
    
    void TreeNode::setChildren(TreeNode* child)
    {
        children.push_back(child);
    }
    
    void TreeNode::depthFirstTraversal()
    {
            if(children.empty())
            {
            }
            else
            {
                children.front();
            }
    }
    
    /*
    void TreeNode::iterativeDeepeningSearch()
    {
        if(left != NULL && right != NULL)
        {
            if(label == NULL)
            {
                cout << label << endl;
            }
            cout << left->label << endl;
            cout << right->label << endl;
            left->iterativeDeepeningSearch();
            right->iterativeDeepeningSearch();
        }
    }
    */
    Main File
    Code:
    #include <iostream>
    #include "TreeNode.h"
    
    using namespace std;
    
    TreeNode* createTree();
    
    int main (int argc, char * const argv[])
    {
        cout << "Creating tree..." << endl;
    
            TreeNode* tree = createTree();
    
        cout << "Depth first traversal..." << endl;
    
            tree->depthFirstTraversal();
    
        cout << "Iterative deepening search..." << endl;
            tree->iterativeDeepeningSearch();
    
            system("pause");
    
            delete tree;
    
    }
    
    
    TreeNode* createTree()
    {
        TreeNode* a = new TreeNode('A');
        TreeNode* b = new TreeNode('B');
        TreeNode* c = new TreeNode('C');
        TreeNode* d = new TreeNode('D');
        TreeNode* e = new TreeNode('E');
        TreeNode* f = new TreeNode('F');
        TreeNode* g = new TreeNode('G');
        TreeNode* h = new TreeNode('H');
        TreeNode* i = new TreeNode('I');
    
        // This function is currently unfinished, still requires a a->setChildren(TreeNode* node)
        return a;
    }

  2. #2
    Registered User
    Join Date
    Mar 2007
    Posts
    416
    Put a 'return 0;' at the end of your int main().

    Are you using the list as your tree node holder? It appears to be a good solution, but yet I didn't compile or run it. Another alternative would be using vector<TreeNode*> so you can access any of the children using [] without having to pop or push anything.

    Is 'label' the only data the nodes hold?

  3. #3
    Registered User
    Join Date
    Aug 2009
    Posts
    2
    I am afraid this kind of linklist is a potential source of memory leaks
    Code:
    list<TreeNode*> children;
    I prefer a smart pointer rather than a naked one in this case, i.e
    Code:
    list<shared_ptr<TreeNode> > children;

  4. #4
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by scwizzo View Post
    Put a 'return 0;' at the end of your int main().
    There's no reason for this. You don't have to do return 0 in main in C++.

  5. #5
    Registered User
    Join Date
    Aug 2009
    Posts
    2
    Are you using the list as your tree node holder? It appears to be a good solution, but yet I didn't compile or run it. Another alternative would be using vector<TreeNode*> so you can access any of the children using [] without having to pop or push anything.
    Hmmm... yes I was thinking of using a vector<TreeNode*>. I choose list because it was the teachers suggestion, but I'll try the vector and see what happens.

    Thanks everyone for replying, I'll take into consideration what you guys have said and see what happens with it. at least i know I'm heading in the right direction

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. MDI children always maximized?
    By Devils Child in forum Windows Programming
    Replies: 4
    Last Post: 02-25-2009, 07:43 AM
  2. Linux Putting my children to sleep with futex!?
    By Abs in forum Linux Programming
    Replies: 18
    Last Post: 02-12-2009, 06:43 PM
  3. forks and children
    By suigeneris in forum C Programming
    Replies: 1
    Last Post: 01-22-2005, 05:48 AM
  4. "Which parent has children with no children"?!?
    By SMurf in forum C Programming
    Replies: 2
    Last Post: 04-28-2003, 01:59 PM
  5. Training children to commit suicide.
    By Liger86 in forum A Brief History of Cprogramming.com
    Replies: 28
    Last Post: 02-06-2003, 09:59 PM