Insert Tree

[JackDurden]

Would someone be so kind as to help me with this insert. The function insert takes two numbers, num and num2. num is the number to insert in the tree and num2 is the number of children to the parent node where num is inserted. I am getting errors for root->children = NULL. Here is what I have.

this is my tree base:

struct node
	{
		node *parent;
		vector <node*> children;
		int item;
	};
node* root;

And my insert function:

void Tree::insert(int num, int num2)
{
	if(isEmpty())
	{
		root = new node;
		root->children = NULL;
		root->item = num;
	}
	else if(root->children == NULL)
	{
		root->children = num;

		for(int i = 0;i<num2;i++)
		{
			children = root;
			root->children = NULL;
		}
	}
	else
		root->children = num;
}

[Sky Diploma]

Childen is of type vector. I think that you should use push_back(value); to handle that.

[JackDurden]

Ah yeah that was just a blind man that didnt notice that. But now, how would I check for an open node?

void Tree::insert(int num, int num2)
{
	if(isEmpty())
	{
		root = new node;
		root->children.push_back(NULL);
		root->item = num;
	}
	else if(root->children == NULL)//here
	{
		root->children.push_back(num);

		for(int i = 0;i<num2;i++)
		{
			children = root;
			root->children.push_back(NULL);
		}
	}
	else
		root->children.push_back(num);
}

[VernonDozier]

Still doesn't make sense to me. Why would you push an integer onto a vector of node* ? Seems to me you should push a pointer to a node onto that vector.

[JackDurden]

Something like this?

void Tree::insert(int num, int num2)
{
	node* insert = new node;
	insert->item = num;

	if(isEmpty())
	{
		root = insert;
		for(int i = 0;i<num2;i++)
		{
			root->children.push_back(0);
		}
	}
	else 
	{ 
		
	}
}

[VernonDozier]

Something like this?

void Tree::insert(int num, int num2)
{
	node* insert = new node;
	insert->item = num;

	if(isEmpty())
	{
		root = insert;
		for(int i = 0;i<num2;i++)
		{
			root->children.push_back(0);
		}
	}
	else 
	{ 
		
	}
}

Well, 0 means NULL and NULL is a pointer, so there's no error there. But I prefer to use the word "NULL" so it's obvious that it's being used as a pointer, not as the integer 0.

This is confusing.

void Tree::insert(int num, int num2)
{
	node* insert = new node;
	insert->item = num;

I'd pick a different name for your new node. It's the same as your function's name. How about newNode ?

void Tree::insert(int num, int num2)
{
	node* newNode = new node;
	newNode->item = num;

The whole function looks fairly odd to me. I think I'd have to see the larger Tree class and the main function to get a better feel for how you're trying to use it.

[JackDurden]

Here is the whole thing...

class Tree
{
public:
	Tree() { root = NULL; }

	bool isEmpty() const { return root==NULL; }
	void insert(int, int);
	
private:
	struct node
	{
		node *parent;
		vector <node*> children;
		int item;
	};
node* root;
};

void Tree::insert(int num, int num2)
{
	node* current = new node;
	current->item = num;

	if(isEmpty())
	{
		root = current;
		for(int i = 0;i<num2;i++)
		{
			root->children.push_back(NULL);
		}
	}
	else 
	{ 
		
	}
}

int main()
{
	Tree myTree;

	myTree.insert(1, 3);

return 0;
}

i want to do something like this for my insert function:

-open node?
if no
make new node and insert num to node
create children to that node based on num2
if yes
find open node, insert num to that node
create children to that node

It looks confusing because im not sure how to do it.

[Sky Diploma]

Well vectors can be handled in majorly in 2 ways. One is to use an index as we do to an array and the other to use iterators.

for example assuming that the for loop in your insert function creates Null pointers which are to be filled here is what you can do.

for(int x=0;x<root->children.size();x++)
{
 if(root->children[x]==NULL)
 {
  //Assign a value
 }
}

[VernonDozier]

My strong advice is to draw it out step-by step. Your tree is going to have children of children of children. Sky Diploma is on to something with his traversal idea, but you need to go further. In particular, dealing with children of children, make sure you are cautious about hard-coding root in the code.

for(int x=0;x<root->children.size();x++)
{
 if(root->children[x]==NULL)
 {
  //Assign a value
 }
}

You need to be able to check children of children and children of children of children and children of children of children of children, etc., which this cannot do. So at some point you may want to have a variable called parentNode (intentionally not named parent to avoid confusion with one of your node members), so you may want to have something like what Sky Diploma has, but replace root with parentNode . parentNode may START OFF being root , but it should potentially also be able to NOT point to root and instead point to some node that is lower in the tree.