943,917 Members | Top Members by Rank

Software Development > C++ > Insert Tree
Ad:
  • C++ Discussion Thread
  • Unsolved
  • Views: 529
  • C++ RSS
Permalink
Jun 9th, 2009
0

Insert Tree

Expand Post »
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:
C++ Syntax (Toggle Plain Text)
  1. struct node
  2. 	{
  3. 		node *parent;
  4. 		vector <node*> children;
  5. 		int item;
  6. 	};
  7. node* root;
And my insert function:
C++ Syntax (Toggle Plain Text)
  1. void Tree::insert(int num, int num2)
  2. {
  3. 	if(isEmpty())
  4. 	{
  5. 		root = new node;
  6. 		root->children = NULL;
  7. 		root->item = num;
  8. 	}
  9. 	else if(root->children == NULL)
  10. 	{
  11. 		root->children = num;
  12.  
  13. 		for(int i = 0;i<num2;i++)
  14. 		{
  15. 			children = root;
  16. 			root->children = NULL;
  17. 		}
  18. 	}
  19. 	else
  20. 		root->children = num;
  21. }
Similar Threads
Reputation Points: 10
Solved Threads: 0
Junior Poster in Training
JackDurden is offline Offline
92 posts
since Jun 2008
Permalink
Jun 9th, 2009
0

Re: Insert Tree

Childen is of type vector. I think that you should use push_back(value); to handle that.
Reputation Points: 673
Solved Threads: 125
Practically a Posting Shark
Sky Diploma is offline Offline
818 posts
since Mar 2008
Permalink
Jun 9th, 2009
0

Re: Insert Tree

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

C++ Syntax (Toggle Plain Text)
  1. void Tree::insert(int num, int num2)
  2. {
  3. 	if(isEmpty())
  4. 	{
  5. 		root = new node;
  6. 		root->children.push_back(NULL);
  7. 		root->item = num;
  8. 	}
  9. 	else if(root->children == NULL)//here
  10. 	{
  11. 		root->children.push_back(num);
  12.  
  13. 		for(int i = 0;i<num2;i++)
  14. 		{
  15. 			children = root;
  16. 			root->children.push_back(NULL);
  17. 		}
  18. 	}
  19. 	else
  20. 		root->children.push_back(num);
  21. }
Reputation Points: 10
Solved Threads: 0
Junior Poster in Training
JackDurden is offline Offline
92 posts
since Jun 2008
Permalink
Jun 9th, 2009
0

Re: Insert Tree

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.
Last edited by VernonDozier; Jun 9th, 2009 at 2:45 pm.
Featured Poster
Reputation Points: 2614
Solved Threads: 687
Posting Expert
VernonDozier is offline Offline
5,375 posts
since Jan 2008
Permalink
Jun 9th, 2009
0

Re: Insert Tree

Something like this?

C++ Syntax (Toggle Plain Text)
  1. void Tree::insert(int num, int num2)
  2. {
  3. 	node* insert = new node;
  4. 	insert->item = num;
  5.  
  6. 	if(isEmpty())
  7. 	{
  8. 		root = insert;
  9. 		for(int i = 0;i<num2;i++)
  10. 		{
  11. 			root->children.push_back(0);
  12. 		}
  13. 	}
  14. 	else 
  15. 	{ 
  16.  
  17. 	}
  18. }
Reputation Points: 10
Solved Threads: 0
Junior Poster in Training
JackDurden is offline Offline
92 posts
since Jun 2008
Permalink
Jun 9th, 2009
0

Re: Insert Tree

Click to Expand / Collapse  Quote originally posted by JackDurden ...
Something like this?

C++ Syntax (Toggle Plain Text)
  1. void Tree::insert(int num, int num2)
  2. {
  3. 	node* insert = new node;
  4. 	insert->item = num;
  5.  
  6. 	if(isEmpty())
  7. 	{
  8. 		root = insert;
  9. 		for(int i = 0;i<num2;i++)
  10. 		{
  11. 			root->children.push_back(0);
  12. 		}
  13. 	}
  14. 	else 
  15. 	{ 
  16.  
  17. 	}
  18. }

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.
Featured Poster
Reputation Points: 2614
Solved Threads: 687
Posting Expert
VernonDozier is offline Offline
5,375 posts
since Jan 2008
Permalink
Jun 9th, 2009
0

Re: Insert Tree

Here is the whole thing...

C++ Syntax (Toggle Plain Text)
  1. class Tree
  2. {
  3. public:
  4. 	Tree() { root = NULL; }
  5.  
  6. 	bool isEmpty() const { return root==NULL; }
  7. 	void insert(int, int);
  8.  
  9. private:
  10. 	struct node
  11. 	{
  12. 		node *parent;
  13. 		vector <node*> children;
  14. 		int item;
  15. 	};
  16. node* root;
  17. };
  18.  
  19. void Tree::insert(int num, int num2)
  20. {
  21. 	node* current = new node;
  22. 	current->item = num;
  23.  
  24. 	if(isEmpty())
  25. 	{
  26. 		root = current;
  27. 		for(int i = 0;i<num2;i++)
  28. 		{
  29. 			root->children.push_back(NULL);
  30. 		}
  31. 	}
  32. 	else 
  33. 	{ 
  34.  
  35. 	}
  36. }
  37.  
  38. int main()
  39. {
  40. 	Tree myTree;
  41.  
  42. 	myTree.insert(1, 3);
  43.  
  44. return 0;
  45. }

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.
Reputation Points: 10
Solved Threads: 0
Junior Poster in Training
JackDurden is offline Offline
92 posts
since Jun 2008
Permalink
Jun 9th, 2009
0

Re: Insert Tree

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.

C++ Syntax (Toggle Plain Text)
  1. for(int x=0;x<root->children.size();x++)
  2. {
  3.  if(root->children[x]==NULL)
  4.  {
  5.   //Assign a value
  6.  }
  7. }
Reputation Points: 673
Solved Threads: 125
Practically a Posting Shark
Sky Diploma is offline Offline
818 posts
since Mar 2008
Permalink
Jun 9th, 2009
1

Re: Insert Tree

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.
Featured Poster
Reputation Points: 2614
Solved Threads: 687
Posting Expert
VernonDozier is offline Offline
5,375 posts
since Jan 2008

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in C++ Forum Timeline: Exam Q: Using Enumerations
Next Thread in C++ Forum Timeline: Issue with returning an int from an array





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC