446,421 Members | 1,127 Online Need help? Post your question and get tips & solutions from a community of 446,421 IT Pros & Developers. It's quick & easy.

# How to sum the determination of a pointer(s)

 P: n/a Hello All, Yes this is homework, but I have spent a lot of time on it and I am close. I want to be able to count the number of nodes in a tree that have only one child. I can identify the nodes with the following code, but I don't know how to sum them up and return that value to the calling function in main(). I know the algorithm is recursive in nature, but I get gibberish for return values. I hope someone can please Help??? Here is the code and the calling function which sends the root of a tree. I have tried iterating oneChildCount and it returns extremely large values. The BST nodes are char. template int countOneChild(tnodeleft); // descend left countOneChild(t->right); // descend right if ((t->left != NULL && t->right == NULL) || (t->left == NULL && t->right != NULL)) oneChildCount = 1; else oneChildCount = 0; cout << oneChildCount << endl; return oneChildCount; } } Calling Function is cout << "Number of interior nodes with one child in Tree 1 is " << countOneChild (root1) << endl; I would appreciate any help, Thanx in advance, A.J. Johnston Jul 8 '06 #1
15 Replies

 P: n/a aj*@rextrax.com wrote: Hello All, Yes this is homework, but I have spent a lot of time on it and I am close. I want to be able to count the number of nodes in a tree that have only one child. I can identify the nodes with the following code, but I don't know how to sum them up and return that value to the calling function in main(). I know the algorithm is recursive in nature, but I get gibberish for return values. I hope someone can please Help??? Here is the code and the calling function which sends the root of a tree. I have tried iterating oneChildCount and it returns extremely large values. The BST nodes are char. template int countOneChild(tnodeleft); // descend left countOneChild(t->right); // descend right You don't do anything with the return values from these calls. I assume you want to add them to oneChildCount. > if ((t->left != NULL && t->right == NULL) || (t->left == NULL && t->right != NULL)) oneChildCount = 1; else oneChildCount = 0; cout << oneChildCount << endl; return oneChildCount; } } If you want help with some code, you should post enough that it can be compiled. -- Ian Collins. Jul 8 '06 #2

 P: n/a aj*@rextrax.com wrote: Hello All, Yes this is homework, but I have spent a lot of time on it and I am close. I want to be able to count the number of nodes in a tree that have only one child. I can identify the nodes with the following code, but I don't know how to sum them up and return that value to the calling function in main(). I know the algorithm is recursive in nature, but I get gibberish for return values. I hope someone can please Help??? Here is the code and the calling function which sends the root of a tree. I have tried iterating oneChildCount and it returns extremely large values. The BST nodes are char. template int countOneChild(tnodeleft); // descend left countOneChild(t->right); // descend right if ((t->left != NULL && t->right == NULL) || (t->left == NULL && t->right != NULL)) oneChildCount = 1; else oneChildCount = 0; cout << oneChildCount << endl; return oneChildCount; } } Calling Function is cout << "Number of interior nodes with one child in Tree 1 is " << countOneChild (root1) << endl; I would appreciate any help, Thanx in advance, A.J. Johnston I'm not surprised since you haven't initialised any of the local variables. The compiler will allocate storage for them but the value can be anything and you want them all to be specifically 0, at least initially. Declare them like this: int oneChildCount(0); int leftChildCount(0); int rightChildCount(0); This will guarantee that the counts have sensible values on function entry. Why have you declared leftChildCount and rightChildCount when they do not appear to be used within the function? oneChildCount does not appear to be incremented anywhere. Presumably, you want to count the number of tree nodes having just one child? As far as I can see oneChildCount will either have a nonsense value or 1 for each recursive invocation of countOneChild whereas it should be zero initially and then increment for each tnode having only one child. The function would then return 0 (there are no one child nodes) or some positive number equal to the number of one child nodes in the tree. There is also no return statement at the end of the function. What happens if t happens to be zero? What value is returned? There is no gurantee that the function will return anything sensible. The function does not modify a tnode so why isn't the argument declared as tnode* ? I wouldn't use a plain int here since: a) you don't know its size and it might overflow for large trees; and b) it's not really what you want. What you want is a count type - yes it's a number but it's closer to the problem domain. I would do something like: typedef std::size_t TreeNodeCount; and then declare the function to be of type TreeNodeCount. You could do this like this: template TreeNodeCount countOneChild (TreeNode

 P: n/a Jim, you have some good points Declare them like this: int oneChildCount(0); Done. Why have you declared leftChildCount and rightChildCount when they do not appear to be used within the function? These variables have been deleted, they were used in a former version oneChildCount does not appear to be incremented anywhere. Presumably, you want to count the number of tree nodes having just one child? As far as I can see oneChildCount will either have a nonsense value or 1 for each recursive invocation of countOneChild whereas it should be zero initially and then increment for each tnode having only one child. The function would then return 0 (there are no one child nodes) or some positive number equal to the number of one child nodes in the tree. I am now incrementing oneChildCount as follows oneChildCount++; > There is also no return statement at the end of the function. What happens if t happens to be zero? What value is returned? There is no gurantee that the function will return anything sensible. I am using the statement return oneChildCount; > The function does not modify a tnode so why isn't the argument declared as tnode* ? Defined parameter. May not be modified. > I wouldn't use a plain int here since: a) you don't know its size and it might overflow for large trees; and b) it's not really what you want. What you want is a count type - yes it's a number but it's closer to the problem domain. I would do something like: typedef std::size_t TreeNodeCount; and then declare the function to be of type TreeNodeCount. You could do this like this: template TreeNodeCount countOneChild (TreeNode int countOneChild(tnode Why are you using the NULL macro? There is no need to since the standard guarantees that binary 0 is compatible with any pointer. NULL is a hangover from C and this is C++. Good to know :) Good point! Eradicated > There are no compilation errors Any more help would be wonderful!!! Sincerely, Aaron Johnston Jul 9 '06 #5

 P: n/a aj*@rextrax.com wrote: Jim, you have some good points Declare them like this: int oneChildCount(0); Done. Why have you declared leftChildCount and rightChildCount when they do not appear to be used within the function? These variables have been deleted, they were used in a former version oneChildCount does not appear to be incremented anywhere. Presumably, you want to count the number of tree nodes having just one child? As far as I can see oneChildCount will either have a nonsense value or 1 for each recursive invocation of countOneChild whereas it should be zero initially and then increment for each tnode having only one child. The function would then return 0 (there are no one child nodes) or some positive number equal to the number of one child nodes in the tree. I am now incrementing oneChildCount as follows oneChildCount++; There is also no return statement at the end of the function. What happens if t happens to be zero? What value is returned? There is no gurantee that the function will return anything sensible. I am using the statement return oneChildCount; The function does not modify a tnode so why isn't the argument declared as tnode* ? Defined parameter. May not be modified. I wouldn't use a plain int here since: a) you don't know its size and it might overflow for large trees; and b) it's not really what you want. What you want is a count type - yes it's a number but it's closer to the problem domain. I would do something like: typedef std::size_t TreeNodeCount; and then declare the function to be of type TreeNodeCount. You could do this like this: template TreeNodeCount countOneChild (TreeNode int countOneChild(tnodeleft == 0) && (t->right ==0)) { // single node with no children return 0; } Also, if we want to be "cute" we can take advantage of the short-circuit nature of boolean operators in C++ (assuming they haven't been overloaded for this class) and collapse the two tests into 1 as follows: if ((t == 0) || ((t->left == 0) && (t->right == 0))) return 0; Note how we can get way with this here because short-circuit rules guarantee left-to-right evaluation order. In other languages where short-circuit evaluation is not done this would likely generate a core dump since the second half of the expression might be referencing through a null pointer if t is actually 0. Of course this violates the one-entry : one-exit rule of structured programing and your teacher might not find that acceptable. He / she might not accept relying on short-circuit evaluation order either since it may cause confusion in other circumstances (remember that in general C++ does not guarantee that an arbitrary expression will be evaluated in a specific order). Don't do this if you're in any doubt about what your teacher will accept! Hope this helps. Cheers Jim. Jul 9 '06 #6

 P: n/a jbannon wrote: aj*@rextrax.com wrote: Jim, you have some good points Declare them like this: > int oneChildCount(0); > Done. Why have you declared leftChildCount and rightChildCount when they do not appear to be used within the function? These variables have been deleted, they were used in a former version oneChildCount does not appear to be incremented anywhere. Presumably, you want to count the number of tree nodes having just one child? As far as I can see oneChildCount will either have a nonsense value or 1 for each recursive invocation of countOneChild whereas it should be zero initially and then increment for each tnode having only one child. The function would then return 0 (there are no one child nodes) or some positive number equal to the number of one child nodes in the tree. I am now incrementing oneChildCount as follows oneChildCount++; > There is also no return statement at the end of the function. What happens if t happens to be zero? What value is returned? There is no gurantee that the function will return anything sensible. I am using the statement return oneChildCount; > The function does not modify a tnode so why isn't the argument declared as tnode* ? Defined parameter. May not be modified. > I wouldn't use a plain int here since: a) you don't know its size and it might overflow for large trees; and b) it's not really what you want. What you want is a count type - yes it's a number but it's closer to the problem domain. I would do something like: > typedef std::size_t TreeNodeCount; > and then declare the function to be of type TreeNodeCount. You could do this like this: > template TreeNodeCount countOneChild (TreeNode since countOneChild will never modify a tree node and, presumably, will not alter the internal state of the class. Note that I have used a reference rather than a pointer here. You would need to modify the code to take account of that or just use the pointer. I have successfuly implemented a solution in this fashion (the one with a reference) however, I am unable to find a solution with the requirements listed below. Write a function template int countOneChild(tnode Why are you using the NULL macro? There is no need to since the standard guarantees that binary 0 is compatible with any pointer. NULL is a hangover from C and this is C++. Good to know :) Good point! Eradicated > There are no compilation errors Any more help would be wonderful!!! Sincerely, Aaron Johnston Aaron, I'm only at the beginning stage myself and it is some time since I looked at recursive functions, but I'll have a go. I think that the problem lies in what happens to count across recursive calls. The question we should ask is the value of oneChildCount preserved across recursive invocations of the function? I'm trying to remember recursive function theory and I think that the value of count is not preserved (the experts will crucify me if I'm wrong). Each time the function recurses, a new copy of count is pushed onto the stack as part of the stack frame so this would indicate that our count needs to be of static storage duration. Therefore, modifying our declaration of count to be something like static int oneChildCount(0); should solve the problem. This means that whenever we execute the statement ++oneChildCount; it is the static variable that is being updated preserving its value across recursive invocations. The final statement in the function should then be return oneChildCount; What's worrying me though is what happens when we call the function again with a different node. Since this would effectively be a new execution environment it should reset oneChildCount but I'm not sure. Any expert opinion please? P.S. I would modify the function slightly to eliminate the 2 simplest cases first: a null node; and a node with no children. I would do this before attempting a recursive call like this: if (t == 0) { // empty tree return 0; } if ((t->left == 0) && (t->right ==0)) { // single node with no children return 0; } Also, if we want to be "cute" we can take advantage of the short-circuit nature of boolean operators in C++ (assuming they haven't been overloaded for this class) and collapse the two tests into 1 as follows: if ((t == 0) || ((t->left == 0) && (t->right == 0))) return 0; Note how we can get way with this here because short-circuit rules guarantee left-to-right evaluation order. In other languages where short-circuit evaluation is not done this would likely generate a core dump since the second half of the expression might be referencing through a null pointer if t is actually 0. Of course this violates the one-entry : one-exit rule of structured programing and your teacher might not find that acceptable. He / she might not accept relying on short-circuit evaluation order either since it may cause confusion in other circumstances (remember that in general C++ does not guarantee that an arbitrary expression will be evaluated in a specific order). Don't do this if you're in any doubt about what your teacher will accept! Hope this helps. Cheers Jim. Nuts! I boobed! Ignore the last bit as it's not correct. What happens if, during a recursive invocation, both t->left and t->right are 0? What we should do is return the value of oneChildCount, not 0! Apologies. Sheesh! Jul 9 '06 #7

 P: n/a Aaron, I'm only at the beginning stage myself and it is some time since I looked at recursive functions, but I'll have a go. I think that the problem lies in what happens to count across recursive calls. The question we should ask is the value of oneChildCount preserved across recursive invocations of the function? I'm trying to remember recursive function theory and I think that the value of count is not preserved (the experts will crucify me if I'm wrong). Each time the function recurses, a new copy of count is pushed onto the stack as part of the stack frame so this would indicate that our count needs to be of static storage duration. Therefore, modifying our declaration of count to be something like static int oneChildCount(0); should solve the problem. This means that whenever we execute the statement ++oneChildCount; it is the static variable that is being updated preserving its value across recursive invocations. The final statement in the function should then be return oneChildCount; What's worrying me though is what happens when we call the function again with a different node. Since this would effectively be a new execution environment it should reset oneChildCount but I'm not sure. Any expert opinion please? The static int was a good idea, the value is persistent though, and so subsequent calls to the same function are summed. So in this case the second call would start with oneChildCount with a value of "2." Any more ideas. I really do appreciate all the help so far. Aaron Johnston Also, if we want to be "cute" we can take advantage of the short-circuit nature of boolean operators in C++ (assuming they haven't been overloaded for this class) and collapse the two tests into 1 as follows: if ((t == 0) || ((t->left == 0) && (t->right == 0))) return oneChildCount; This is fine and good programming practice as far as I understand. The situation most likely to occur should be stated on the left, so that if it is true, the right side not even need be evaluated. The static int was a good idea, the value is persistent though, and so subsequent calls to the same function are summed. So in this case the second call would start with oneChildCount with a value of "2." Any more ideas. I really do appreciate all the help so far. Aaron Johnston Jul 10 '06 #8

 P: n/a aj*@rextrax.com wrote: Aaron, I'm only at the beginning stage myself and it is some time since I looked at recursive functions, but I'll have a go. I think that the problem lies in what happens to count across recursive calls. The question we should ask is the value of oneChildCount preserved across recursive invocations of the function? I'm trying to remember recursive function theory and I think that the value of count is not preserved (the experts will crucify me if I'm wrong). Each time the function recurses, a new copy of count is pushed onto the stack as part of the stack frame so this would indicate that our count needs to be of static storage duration. Therefore, modifying our declaration of count to be something like > static int oneChildCount(0); > should solve the problem. This means that whenever we execute the statement ++oneChildCount; it is the static variable that is being updated preserving its value across recursive invocations. The final statement in the function should then be return oneChildCount; > What's worrying me though is what happens when we call the function again with a different node. Since this would effectively be a new execution environment it should reset oneChildCount but I'm not sure. Any expert opinion please? The static int was a good idea, the value is persistent though, and so subsequent calls to the same function are summed. So in this case the second call would start with oneChildCount with a value of "2." Any more ideas. I really do appreciate all the help so far. Aaron Johnston > > Also, if we want to be "cute" we can take advantage of the short-circuit nature of boolean operators in C++ (assuming they haven't been overloaded for this class) and collapse the two tests into 1 as follows: > if ((t == 0) || ((t->left == 0) && (t->right == 0))) return oneChildCount; > This is fine and good programming practice as far as I understand. The situation most likely to occur should be stated on the left, so that if it is true, the right side not even need be evaluated. The static int was a good idea, the value is persistent though, and so subsequent calls to the same function are summed. So in this case the second call would start with oneChildCount with a value of "2." Any more ideas. I really do appreciate all the help so far. Aaron Johnston Aaron, We're missing something really obvious but for the life of me I can't see what it is. A really silly test confirms the suspicion: #include int recurse(int n) { static int t(0); ++t; std::cout << "Value of t is " << t << std::endl; if (n == 0) return t; recurse (--n); } int main() { int t1(0); t1 = recurse(10); std::cout << "Value of t1 is " << t1 << std::endl; t1 = recurse(10); std::cout << "Value of t1 is " << t1 << std::endl; return 0; } The problem here is that, as you rightly say, the value continues to accumulate on any subsequent calls and yet, if we remove the static storage specifier the value of t is always 1. Of course, I have not checked for negative n, in which case we would get an infinite loop, but that does not really matter here. I don't think the problem lies in the method of tree traversal. We could do an in-order, pre-order or post-order traversal and end up with the same result so it's not that. But I cannot for the life of me see a way of preserving the count using a recursive traversal algorithm that clears the count on subsequent calls with a new node. Maybe we should be looking at non-recursive methods? Jul 10 '06 #9

 P: n/a jbannon wrote: aj*@rextrax.com wrote: Aaron, I'm only at the beginning stage myself and it is some time since I looked at recursive functions, but I'll have a go. I think that the problem lies in what happens to count across recursive calls. The question we should ask is the value of oneChildCount preserved across recursive invocations of the function? I'm trying to remember recursive function theory and I think that the value of count is not preserved (the experts will crucify me if I'm wrong). Each time the function recurses, a new copy of count is pushed onto the stack as part of the stack frame so this would indicate that our count needs to be of static storage duration. Therefore, modifying our declaration of count to be something like static int oneChildCount(0); This is a bad idea - try passing an object down through the recursion to accumulate the count; google for the "visitor" pattern. Jul 10 '06 #10

 P: n/a tragomaskhalos wrote: jbannon wrote: aj*@rextrax.com wrote: Aaron, I'm only at the beginning stage myself and it is some time since I looked at recursive functions, but I'll have a go. I think that the problem lies in what happens to count across recursive calls. The question we should ask is the value of oneChildCount preserved across recursive invocations of the function? I'm trying to remember recursive function theory and I think that the value of count is not preserved (the experts will crucify me if I'm wrong). Each time the function recurses, a new copy of count is pushed onto the stack as part of the stack frame so this would indicate that our count needs to be of static storage duration. Therefore, modifying our declaration of count to be something like > static int oneChildCount(0); > This is a bad idea - try passing an object down through the recursion to accumulate the count; google for the "visitor" pattern. Yeah, a visitor would do the job (having just looked it up). Don't quite know how it would be done though but it's worth having a go. Thanks Jim. Jul 10 '06 #11

 P: n/a aj*@rextrax.com wrote: Hello All, Yes this is homework, but I have spent a lot of time on it and I am close. I want to be able to count the number of nodes in a tree that have only one child. I can identify the nodes with the following code, but I don't know how to sum them up and return that value to the calling function in main(). I know the algorithm is recursive in nature, but I get gibberish for return values. I hope someone can please Help??? Here is the code and the calling function which sends the root of a tree. I have tried iterating oneChildCount and it returns extremely large values. The BST nodes are char. template int countOneChild(tnodeleft); // descend left countOneChild(t->right); // descend right if ((t->left != NULL && t->right == NULL) || (t->left == NULL && t->right != NULL)) oneChildCount = 1; else oneChildCount = 0; cout << oneChildCount << endl; return oneChildCount; } } Calling Function is cout << "Number of interior nodes with one child in Tree 1 is " << countOneChild (root1) << endl; I would appreciate any help, Thanx in advance, A.J. Johnston Aaron I've been having a little think about this. What would happen if we wrapped the template function in an auxilliary class whose state was the actual count you're looking for? Something like the following I believe would work (note I haven't tested this or fleshed out the details): template< typename T > class CountChildren { public: CountChildren () : oneChildNodes(0), leftChildNodes(0), rightChildNodes(0) {} size_t oneChildCount (T const& node); size_t leftChildCount (T const& node); size_t rightChildCount (T const& node); ~CountChildren () {} private: size_t oneChildNodes_; size_t leftChildNodes_; size_t rightChildNodes_; }; The destructor doesn't really need to do anything very much since we're only dealing with simple integral types. Implementation of the functions would then follow the recursive tree traversal method already discussed except that instead of updating a static variable, they update the private counts. Anyone any thoughts on this strategy? Cheers Jim. Jul 12 '06 #12

 P: n/a James Bannon wrote: aj*@rextrax.com wrote: >Hello All,Yes this is homework, but I have spent a lot of time on it and I amclose.I want to be able to count the number of nodes in a tree that have onlyone child.I can identify the nodes with the following code, but I don't know howto sum them up and return that value to the calling function in main(). I know the algorithm is recursive in nature, but I get gibberish forreturn values. I hope someone can please Help???Here is the code and the calling function which sends the root of atree. I have tried iterating oneChildCount and it returns extremelylarge values. The BST nodes are char.template int countOneChild(tnodeleft); // descend left countOneChild(t->right); // descend right if ((t->left != NULL && t->right == NULL) || (t->left == NULL&& t->right != NULL)) oneChildCount = 1; else oneChildCount = 0; cout << oneChildCount << endl; return oneChildCount; }}Calling Function is cout << "Number of interior nodes with one child in Tree 1 is " < class CountChildren { public: CountChildren () : oneChildNodes(0), leftChildNodes(0), rightChildNodes(0) {} size_t oneChildCount (T const& node); size_t leftChildCount (T const& node); size_t rightChildCount (T const& node); ~CountChildren () {} private: size_t oneChildNodes_; size_t leftChildNodes_; size_t rightChildNodes_; }; The destructor doesn't really need to do anything very much since we're only dealing with simple integral types. Implementation of the functions would then follow the recursive tree traversal method already discussed except that instead of updating a static variable, they update the private counts. Anyone any thoughts on this strategy? Cheers Jim. Correction. The constructor should read: CountChildren(): oneChildNodes_(0), leftChildNodes_(0), rightChildNodes(0) {} Sorry about that! Cheers Jim Jul 12 '06 #13

 P: n/a A,J I think you need to modify this function like this: template int countOneChild(tnodeleft); // descend left countOneChild(t->right); // descend right if ((t->left != NULL && t->right == NULL){ oneChildCount = countOneChild(t->left) + 1; //descend left } else if ((t->left == NULL&& t->right != NULL)){ oneChildeCount++; oneChildCount += countOneChild(t->right); //descend right } else oneChildCount += (countOneChild(t->left) + countOneChilde(t->right)); } cout << oneChildCount << endl; return oneChildCount; } Sorry, I did't test it with your other code. Vacu Jul 26 '06 #14

 P: n/a vacu

 P: n/a Reposting with quotate text and clarify *this function" to actual function name, hope it is clear this time. A,J I think you need to modify template int countOneChild(tnodeleft); // descend left countOneChild(t->right); // descend right if ((t->left != NULL && t->right == NULL){ oneChildCount = countOneChild(t->left) + 1; //descend left } else if ((t->left == NULL&& t->right != NULL)){ oneChildeCount++; oneChildCount += countOneChild(t->right); //descend right } else oneChildCount += (countOneChild(t->left) + countOneChilde(t->right)); } cout << oneChildCount << endl; return oneChildCount; } Sorry, I did't test it with your other code. Vacu aj*@rextrax.com wrote: Hello All, Yes this is homework, but I have spent a lot of time on it and I am close. I want to be able to count the number of nodes in a tree that have only one child. I can identify the nodes with the following code, but I don't know how to sum them up and return that value to the calling function in main(). I know the algorithm is recursive in nature, but I get gibberish for return values. I hope someone can please Help??? Here is the code and the calling function which sends the root of a tree. I have tried iterating oneChildCount and it returns extremely large values. The BST nodes are char. template int countOneChild(tnodeleft); // descend left countOneChild(t->right); // descend right if ((t->left != NULL && t->right == NULL) || (t->left == NULL && t->right != NULL)) oneChildCount = 1; else oneChildCount = 0; cout << oneChildCount << endl; return oneChildCount; } } Calling Function is cout << "Number of interior nodes with one child in Tree 1 is " << countOneChild (root1) << endl; I would appreciate any help, Thanx in advance, A.J. Johnston Jul 27 '06 #16

### This discussion thread is closed

Replies have been disabled for this discussion. 