二叉树的祖先 [英] Binary tree ancestor

问题描述

必须说问题1是否是二叉树中问题2的祖先

it must say if question1 is an ancestor of question2 in a binary tree

#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）的两个节点来解决。当我调试时，我看到在返回true语句后它进入else块并递归遍历二叉树。为什么会这样？

What I have tried:

I have tried to solve by two nodes pointing to the first node(start and root). when I debug, I see that after return true statement it goes inside else block and recursively traverses binary tree again. why is it like that?

推荐答案

您的二叉树搜索过程有问题。 规范二叉树搜索过程的工作方式如下：



BinarySearch （TreeNode * currentNode）



1.如果currentNode为NULL，则返回失败。

2.如果currentNode是你想要的那个，返回成功。

3.如果 BinarySearch （currentNode->; left）成功，返回成功。

4.返回 BinarySearch （currentNode->右）



现在想想。为了使'question1'成为'question2'的祖先，什么条件一定是真的？

Your binary tree search procedure is faulty. The 'canonical' binary tree search procedure works like this:

BinarySearch(TreeNode* currentNode)

1. If currentNode is NULL, return failure.
2. If currentNode is the one that you want, return success.
3. If BinarySearch(currentNode->left) succeeded, return success.
4. Return BinarySearch(currentNode->right)

Now think. In order for 'question1' to be an ancestor of 'question2', what conditions must be true?

这篇关于二叉树的祖先的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！