# TreeNodes for more than two children

• 08-15-2009
Bezarath
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:

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;
}

• 08-15-2009
scwizzo
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?
• 08-15-2009
fallening
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;
• 08-15-2009
EVOEx
Quote:

Originally Posted by scwizzo
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++.
• 08-15-2009
Bezarath
Quote:

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 :)