c++ - 如何在给定特定节点的 BST 中找到直接较大的元素？

Question

<分区>

Answer 1

所以基本上你想要给定节点的顺序后继:下面是解决方案:

struct node * inOrderSuccessor(struct node *root, struct node *n) 
{ 

    if( n->right != NULL ) 
        return minValue(n->right); 

    struct node *succ = NULL; 

    // Start from root and search for successor down the tree 
    while (root != NULL) 
    { 
        if (n->data < root->data) 
        { 
            succ = root; 
            root = root->left; 
        } 
        else if (n->data > root->data) 
            root = root->right; 
        else
           break; 
    } 

    return succ; 
} 

算法逻辑为(不需要父节点指针):

1) 如果节点的右子树不为NULL，则succ在右子树中。做以下。 转到右子树并返回右子树中具有最小键值的节点。

2) 如果节点的右子树为NULL，则从根开始，使用类搜索技术。做以下。 沿着树向下移动，如果一个节点的数据大于根的数据，则向右走，否则向左走。