C++ RSS C++ RSS

Find first NULL

Please support our C++ advertiser: Intel Parallel Studio Home
Reply

•
•
Join Date: Jun 2008
Posts: 92
Reputation: JackDurden is an unknown quantity at this point 
Solved Threads: 0
JackDurden JackDurden is offline Offline
Junior Poster in Training

Find first NULL

 
0
  #1
Jun 13th, 2009
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
Reply With Quote Quick reply to this message  
•
•
Join Date: Mar 2008
Posts: 675
Reputation: Sky Diploma is a splendid one to behold Sky Diploma is a splendid one to behold Sky Diploma is a splendid one to behold Sky Diploma is a splendid one to behold Sky Diploma is a splendid one to behold Sky Diploma is a splendid one to behold 
Solved Threads: 99
Sky Diploma's Avatar
Sky Diploma Sky Diploma is offline Offline
Practically a Master Poster

Re: Find first NULL

 
0
  #2
Jun 13th, 2009
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
1. Please Mark Your Thread as Solved After Getting Your Answers.
2. Please Use CODE TAGS .
Reply With Quote Quick reply to this message  
•
•
Join Date: Jun 2008
Posts: 92
Reputation: JackDurden is an unknown quantity at this point 
Solved Threads: 0
JackDurden JackDurden is offline Offline
Junior Poster in Training

Re: Find first NULL

 
0
  #3
Jun 13th, 2009
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jan 2008
Posts: 3,819
Reputation: VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute 
Solved Threads: 501
Featured Poster
VernonDozier VernonDozier is offline Offline
Senior Poster

Re: Find first NULL

 
2
  #4
Jun 13th, 2009
•
•
•
•
Originally Posted by Sky Diploma View Post
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++.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jun 2008
Posts: 92
Reputation: JackDurden is an unknown quantity at this point 
Solved Threads: 0
JackDurden JackDurden is offline Offline
Junior Poster in Training

Re: Find first NULL

 
0
  #5
Jun 13th, 2009
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: May 2009
Posts: 13
Reputation: rcollins is an unknown quantity at this point 
Solved Threads: 3
rcollins rcollins is offline Offline
Newbie Poster

Re: Find first NULL

 
0
  #6
Jun 13th, 2009
•
•
•
•
Originally Posted by JackDurden View 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);
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.
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the C++ Forum
Thread Tools Search this Thread



api array arrays based binary c++ c/c++ calculator char char* class classes code coding compile console conversion convert count database delete deploy desktop developer directshow dll download dynamic dynamiccharacterarray email encryption error file forms fstream function functions game givemetehcodez google graph gui homeworkhelp iamthwee ifstream input int java lib linkedlist linker linux list loop looping loops map math matrix memory multiple news number numbertoword output pointer problem program programming project python random read recursion recursive reference return rpg sorting string strings temperature template templates test text text-file tree unix url variable vector video visual visualstudio win32 windows winsock wordfrequency wxwidgets
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC