Member 13277493 Ответов: 1

Двоичный древовидный предок


он должен сказать, является ли 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, он снова рекурсивно пересекает двоичное дерево. почему это так?

1 Ответов

Рейтинг:
2

Daniel Pfeffer

Ваша процедура поиска бинарного дерева ошибочна. Процедура поиска "канонического" двоичного дерева работает следующим образом:

Ищет(TreeNode* currentNode)

1. Если currentNode равен NULL, то возвращается ошибка.
2. Если currentNode-это тот, который вы хотите, верните успех.
3. Если Ищет(currentNode->left) successed, return success.
4. Возвращение Ищет(currentNode->справа)

Теперь думать. Чтобы "Вопрос 1" был предком "вопроса 2", Какие условия должны быть истинными?


Member 13277493

Спасибо за помощь. Я должен найти вопрос1 и пересечь левое и правое поддеревья, чтобы найти вопрос2. - да?