943,551 Members | Top Members by Rank

Software Development > C++ > Find first NULL
Ad:
  • C++ Discussion Thread
  • Unsolved
  • Views: 421
  • C++ RSS
Permalink
Jun 13th, 2009
0

Find first NULL

Expand Post »
I want to find the first null child in a tree and return that node of the tree.

Im thinking something like this but it doesnt seem to work the way I want.

C++ Syntax (Toggle Plain Text)
  1. node *Find_Empty_Node(node* root)
  2. {
  3. 	int index = 0;
  4. 	if(root)
  5. 	{
  6. 		if(root->data == 0)//<--I want this child
  7. 				return tree->child[index];
  8.  
  9. 			for(int i = 0;i<root->child.size();i++)
  10. 			{
  11. 				Find_Empty_Node(root->child[i]);
  12. 				index = i;
  13. 			}
  14. 	}
  15. 	return tree;
  16. }

and then back where is called do something like this?

C++ Syntax (Toggle Plain Text)
  1. node* curr = root;
  2. curr = Find_Empty_Node(node* root);
Last edited by JackDurden; Jun 13th, 2009 at 1:07 pm. Reason: code tags
Similar Threads
Reputation Points: 10
Solved Threads: 0
Junior Poster in Training
JackDurden is offline Offline
92 posts
since Jun 2008
Permalink
Jun 13th, 2009
0

Re: Find first NULL

c++ Syntax (Toggle Plain Text)
  1. node *Find_Empty_Node(node* root)
  2. {
  3. 	int index = 0;
  4. 	if(root)
  5. 	{
  6. 		if(root->data == 0)//<--I want this child
  7. 				return tree->child[index];
  8.  
  9. 			for(int i = 0;i<root->child.size();i++)
  10. 			{
  11.                                 index = i;
  12. 				return Find_Empty_Node(root->child[i]);
  13. 			}
  14. 	}
  15. 	return tree;
  16. }

Shouldnt this be the way to do it?
I mean return the Empty Node as this is a example of a Recursive Function.
Last edited by Sky Diploma; Jun 13th, 2009 at 1:45 pm. Reason: Added SOME TEXT
Reputation Points: 673
Solved Threads: 125
Practically a Posting Shark
Sky Diploma is offline Offline
818 posts
since Mar 2008
Permalink
Jun 13th, 2009
0

Re: Find first NULL

Yeah this works...I meant I want it to stop after it finds the first null child. I cant figure out 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 13th, 2009
2

Re: Find first NULL

Click to Expand / Collapse  Quote originally posted by Sky Diploma ...
c++ Syntax (Toggle Plain Text)
  1. node *Find_Empty_Node(node* root)
  2. {
  3. 	int index = 0;
  4. 	if(root)
  5. 	{
  6. 		if(root->data == 0)//<--I want this child
  7. 				return tree->child[index];
  8.  
  9. 			for(int i = 0;i<root->child.size();i++)
  10. 			{
  11.                                 index = i;
  12. 				return Find_Empty_Node(root->child[i]);
  13. 			}
  14. 	}
  15. 	return tree;
  16. }

Shouldnt this be the way to do it?
I mean return the Empty Node as this is a example of a Recursive Function.
Seems to me you need an if-statement in there (around line 12) to check whether Find_Empty_Node has found an empty node. Jack Durden's code goes through the whole loop regardless of whether it finds an empty node. Your code will never go through the whole loop. You want to either go through the whole loop or not depending on whether an empty node is found.

C++ Syntax (Toggle Plain Text)
  1. for(int i = 0;i<root->child.size();i++)
  2. {
  3.     node* nodeFound = Find_Empty_Node(root->child[i]);
  4.     if (nodeFound != NULL && nodeFound->data == 0)
  5.         return nodeFound;
  6. }

I think this function may have some other problems. In particular, I'm not sure it will ever return below the first level of children due to these lines:

C++ Syntax (Toggle Plain Text)
  1. return tree->child[index];

and

C++ Syntax (Toggle Plain Text)
  1. return tree;

I assume tree is the overall root node for the entire tree.
Last edited by VernonDozier; Jun 13th, 2009 at 2:19 pm. Reason: changed "null" to "NULL". Forgot that NULL is capitalized in C++.
Featured Poster
Reputation Points: 2614
Solved Threads: 687
Posting Expert
VernonDozier is offline Offline
5,371 posts
since Jan 2008
Permalink
Jun 13th, 2009
0

Re: Find first NULL

Yeah thats what im trying to do, get it to go through all the levels of the tree until it finds the first null child. I thought like a preorder traversal implementation would do the trick...but its not working.
Reputation Points: 10
Solved Threads: 0
Junior Poster in Training
JackDurden is offline Offline
92 posts
since Jun 2008
Permalink
Jun 13th, 2009
0

Re: Find first NULL

Click to Expand / Collapse  Quote originally posted by JackDurden ...
I want to find the first null child in a tree and return that node of the tree.

Im thinking something like this but it doesnt seem to work the way I want.

C++ Syntax (Toggle Plain Text)
  1. node *Find_Empty_Node(node* root)
  2. {
  3. 	int index = 0;
  4. 	if(root)
  5. 	{
  6. 		if(root->data == 0)//<--I want this child
  7. 				return tree->child[index];
  8.  
  9. 			for(int i = 0;i<root->child.size();i++)
  10. 			{
  11. 				Find_Empty_Node(root->child[i]);
  12. 				index = i;
  13. 			}
  14. 	}
  15. 	return tree;
  16. }

and then back where is called do something like this?

C++ Syntax (Toggle Plain Text)
  1. node* curr = root;
  2. curr = Find_Empty_Node(node* root);
The first real problem I see is that your function takes in a node pointer you call root however if this node is empty or it's data is set to zero you are returning the first child of a node pointed to by tree . I believe you really want a statement like return root->child[index]; .
If you are trying to find a node with data set to 0 do you want to return that so it can be changed to some other data. If this is the case you should actually be returning something like return root; that way that node can be changed to some other data. If you don't change the data in the first node that has data 0 your Find_Empty_Node function will always stop at the same node and over write it's first child.
Also it would be helpful if we knew what results you were trying to get. I hope some of this helps you.
Reputation Points: 10
Solved Threads: 4
Newbie Poster
rcollins is offline Offline
17 posts
since May 2009

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: Best Approach To solve this..
Next Thread in C++ Forum Timeline: Help with FTP uploading using winsock





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


Follow us on Twitter


© 2011 DaniWeb® LLC