Hello to all.

There is a non-binary tree. It is necessary to make the search function of the element in the subtree. Those. find out in which subtree this element lies: in the left or in the right. Here is the bypass function (symmetric, recursive).

int Obxod(ElemT * pCur, int a) { if (pCur != NULL) { if (pCur->pRight != NULL) Obxod(pCur->pRight, a); if (pCur->Sod == a) return 1; if (pCur->pLeft != NULL) Obxod(pCur->pLeft, a); } return -1; }

Help me find a bug. Why the function does not return 1 if it finds an element in the subtree. It always returns -1 in any case. Those. it does not enter the body of the conditional operator at all. / I checked the main key pointers for left / right for NULL - everything is fine. Here is how this function is called for the subtree. A pointer to the subtree and the value to be found are passed to the function.

 cout << "nЛевое поддерево = " << Obxod(pHead->pLeft, ii); cout << "nПравое поддерево = " << Obxod(pHead->pRight, ii);
  • How to fix the situation .. With the left subtree is friends. But in the right subtree it does not see the elements of the right node .. Ie right subtree, right subtree i. subtree))))) - Ruzel
  • Thank you Vladimir for taking the time, for me :-) Everything is now exactly everything works drove through the test. The results are correct. Thank you!) - Ruzel

1 answer 1

At first glance: the recurrent function, it is necessary to process the result of each of its call, to know when to stop. Example (modified to make it easier to read):

 int Obxod (ElemT* pCur, int a) { if(pCur==NULL) return -1; if(pCur->Sod == a) return 1; int local_res(-1); if(pCur->pRight!=NULL) local_res = Obxod(pCur->pRight,a); if(local_res < 0 && pCur->pLeft!=NULL) local_res = Obxod(pCur->pLeft,a); return local_res; }
  • Thanks a lot. It helped. - Ruzel
  • Sorry. But the corrected function does not always find, either. - Ruzel
  • Is element but it returns still -1. - Ruzel
  • Yes, I think the point is this. there is not enough return from the function if the necessary element is found in the right subtree: if(pCur->pRight!=NULL) local_res = Obxod(pCur->pRight,a); else if (local_res>0) return 1; if(pCur->pRight!=NULL) local_res = Obxod(pCur->pRight,a); else if (local_res>0) return 1; - vladimir_ki
  • Now does not find the elements !? Neither the left nor the right! - Ruzel