Двоичный древовидный предок
он должен сказать, является ли question1 предком question2 в двоичном дереве
#include <iostream> #include <string> using namespace std; struct node { string question; node *left, *right; }; node *newNode(string m_question) { node *temp=new node; temp->question=m_question; temp->left=NULL; temp->right=NULL; return temp; } bool is_ancestor(node* start, string question1, string question2) { node *root; if(start==NULL){return false;} if(start->question==question1) { while(start!=NULL) { if(start->left->question==question2) { return true; } else{ start=start->left; } } while(root!=NULL) { if(root->right->question==question2) { return true; } else{ root=root->right; } } } else{ is_ancestor(start->left, question1, question2); is_ancestor(start->right, question1, question2); } } int main() { node *start = newNode("Bob"); node *root=start; string question1="Jack"; string question2="Linda"; start->left = newNode("Jack"); start->right = newNode("Maria"); start->left->left = newNode("Linda"); cout<<is_ancestor(start, question1, question2)<<endl; }
Что я уже пробовал:
Я попытался решить проблему с помощью двух узлов, указывающих на первый узел(start и root). когда я отлаживаю, я вижу, что после того, как оператор return true возвращается в блок else, он снова рекурсивно пересекает двоичное дерево. почему это так?