如何找到给定的整数是否是递归的根的有序继承人？

Question

我知道如何迭代地解决此问题，但是我正在努力地递归地解决它。

我要实现的功能的原型是

bool isInOrder(node * root, int search);

这需要给定根节点，看看整数search是否为后继根。如果是IOS，则返回true。否则返回false。

我知道，为了找到IOS，我需要先向右遍历一个节点，然后一直向左遍历。这是相对简单的迭代操作，但是我怎么只使用递归呢？

不幸的是，我无法访问构建树的代码，因为这是我的教授提供的用于遍历的一组功能的一部分。

我知道树的每个节点都是该类型的

struct node {
    int data;
    node * left;
    node * right;
}

这是典型的二叉搜索树，其中输入数据是随机选择的。

Answer 1

我找到此解决方案以在此link中找到有序的Succesor。因此，大多数答案是link带给我们的解决方案。我建议您检查该链接，以了解它们如何定义结构。现在，有了此功能可以找到有序的Succesor，您可以将代码用于您期望的解决方案。您可以尝试这样的事情：

// function to find left most node in a tree 
Node* leftMostNode(Node* node) 
{ 
    while (node != NULL && node->left != NULL) 
        node = node->left; 
    return node; 
} 

// function to find right most node in a tree 
Node* rightMostNode(Node* node) 
{ 
    while (node != NULL && node->right != NULL) 
        node = node->right; 
    return node; 
} 

// recursive function to find the Inorder Scuccessor 
// when the right child of node x is NULL 
Node* findInorderRecursive(Node* root, Node* x ) 
{ 
    if (!root) 
        return NULL; 

    if (root==x || (temp = findInorderRecursive(root->left,x)) || 
                   (temp = findInorderRecursive(root->right,x))) 
    { 
        if (temp) 
        { 
            if (root->left == temp) 
            { 
                //cout << "Inorder Successor of " << x->data; 
                //cout << " is "<< root->data << "\n"; 
                return NULL; 
            } 
        } 

        return root; 
    } 

    return NULL; 
} 

// function to find inorder successor of  
// a node 
Node* inorderSuccesor(Node* root, Node* x) 
{ 
    // Case1: If right child is not NULL 
    if (x->right != NULL) 
    { 
        Node* inorderSucc = leftMostNode(x->right); 
        //cout<<"Inorder Successor of "<<x->data<<" is "; 
        //cout<<inorderSucc->data<<"\n"; 
        return inorderSucc;
    } 

    // Case2: If right child is NULL 
    if (x->right == NULL) 
    {     
        int f = 0; 

        Node* rightMost = rightMostNode(root); 

        // case3: If x is the right most node 
        if (rightMost == x) {
            //cout << "No inorder successor! Right most node.\n"; 
            return NULL;
        }else
            return findInorderRecursive(root, x); 
    } 
} 
bool isInOrder(node * root, int search){
     bool dummyvar =  (inorderSuccesor(Node* root, Node* root)->data==search) ? true : false;
     return dummyvar;
}