Reputation: 105
I am trying to create a n-ary tree with a vector of the children.
This is what I have gotten so far.
In the node.h file I have this:
#include <vector>
#include <string>
using namespace std;
class Node{
private:
Node *parent;
vector <Node*> children;
int data;
public:
Node();
Node(Node parent, vector<Node> children);
Node(Node parent, vector<Node> children, int data);
Node * GetParent();
void SetChildren(vector<Node> children);
vector<Node>* GetChildren();
void AddChildren(Node children);
void SetData(int data);
int GetData();
bool IsLeaf();
bool IsInternalNode();
bool IsRoot();
};
And this is my node.cpp file.
#include "node.h"
Node::Node(){
this->parent = NULL;
this->children = NULL;
this->data = 0;
}
Node::Node(Node parent, vector<Node> children){
this->parent = &parent;
this->children = &children;
}
Node::Node(Node parent, vector<Node> children, int data){
this->parent = &parent;
this->children = &children;
this->data = data;
}
Node* Node:: GetParent(){
return this->parent;
}
void Node::SetChildren(vector<Node> children){
this->children = &children;
}
vector<Node> * Node::GetChildren(){
return this->children;
}
void Node::AddChildren(Node children){
this->children.push_back(children);
}
void Node::SetData(int data){
this->data = data;
}
This obviously doesn't work. My main problem is that I am not quite sure how to handle the vector for the children. I wrote this following some tutorials online, but as you can see I am super confused.
Upvotes: 1
Views: 17834
Reputation: 203
This implementation of SearchElement
(without recursion) also works:
TreeNode* SearchElement(TreeNode *NextNode, char *data, int& val)
{
bool bVal = false;
for (vector<TreeNode*>::iterator it = NextNode->children.begin(); it != NextNode->children.end(); it++)
{
if ((*it)->value == *(data))
return (*it);
}
return NextNode;
}
TreeNode* res = SearchElement(root, data, value);
I checked this out, not understandable, why - it works for any node you want to find in the tree, no matter the depth and the level of the node in the tree, And that's unclear why, Because the loop iterates only over the children at the second level of the tree (children of the root node), Despite this - it even will find nodes with depth of 10 levels in the tree.
Upvotes: 0
Reputation: 31
Check if below code helps you to create n-array tree creation.
struct TreeNode
{
vector<TreeNode*> children;
char value;
};
class TreeDictionary
{
TreeNode *root;
public:
TreeDictionary()
{
root = new TreeNode();
root->value = 0;
}
TreeNode *CreateNode(char data)
{
TreeNode *parent_node = new TreeNode;
if (parent_node)
parent_node->value = data;
return parent_node;
}
TreeNode* SearchElement(TreeNode *NextNode, char *data, int& val)
{
bool bVal = false;
for (vector<TreeNode*>::iterator it = NextNode->children.begin(); it != NextNode->children.end(); it++)
{
if ((*it)->value == *(data))
return SearchElement((*it), ++data, ++val);
}
return NextNode;
}
TreeNode *InsertNode(TreeNode *parent, TreeNode *ChildNode, char data)
{
if (parent == NULL)
ChildNode = CreateNode(data);
else
{
TreeNode *childNode = CreateNode(data);
parent->children.push_back(childNode);
return childNode;
}
return ChildNode;
}
void InsertMyString(string str)
{
TreeNode *NextNode = root;
for (int i = 0; i < str.size(); i++)
{
if (str[i] == '\0')
return;
cout << str[i] << endl;
if (NextNode->value == 0)
{
NextNode->value = str[i];
continue;
}
else if (NextNode->value != str[i])
{
NextNode = InsertNode(NextNode, NULL, str[i]);
}
else
{
TreeNode *node;
node = SearchElement(NextNode, &str[++i], i);
NextNode = InsertNode(node, NULL, str[i]);
}
}
}
};
int main()
{
TreeDictionary td;
td.InsertMyString("Monster");
td.InsertMyString("Maid");
td.InsertMyString("Monday");
td.InsertMyString("Malli");
td.InsertMyString("Moid");
return 0;
}
Upvotes: 3
Reputation: 10698
The main (and possibly only) problem in your code is that you defined your Node
class to manipulate nodes by pointers (Node*
) :
class Node{
private:
Node *parent;
vector <Node*> children;
But your methods are manipulating nodes by values (Node
).
As instance, in the constructors :
Node::Node(Node parent, vector<Node> children){
this->parent = &parent;
Storing the address of the parent parameter won't work, it's a temporary object, you'll need to pass a Node* parent
to your constructor or to create a new Node object.
this->children = &children;
This doesn't make any sense since this->children
is a vector of Node*
and the children
parameter is a vector of Node
. Again, you'll need to either pass a vector of Node*
to your constructor or to create new node objects.
You have the same issues in SetChildren
and AddChildren
.
Also, since you're manipulating your nodes as pointers, be very careful about the memory management. There's no garbage collector in C++, you'll have to delete
every thing you new
and at the proper time.
Upvotes: 5