c++ - 给定键，如何找到 BST 的某个元素？

Question

所以我正在尝试为 BST 实现一个 TREE_SUCCESSOR(X) 函数，其中 X 是我试图找到其后继节点的键。到目前为止我有这个:

int BinarySearchTree::TREE_SUCCESSOR(node* x)
{
//i dont need a new node, I just need a pointer/reference to x. 
node* y = NULL;
//node* parent = NULL;
if (x->right != NULL)
{
    return FIND_MIN(x->right);
}
else
{
    y = x->parent; 
    while (y != NULL && x == y->right)
    {
        x = y;
        y = y->parent;
    }
    return y->key; 
}
} 

我的问题出在主要功能上:

int main()
{
BinarySearchTree bst;
int num = 0; 
cout << "Enter number you want to find the successor of: " <<endl; 
cin >> num; 

if(BST.root->key == num)             //if i'm trying to find the successor of the root
   { TREE_SUCCESSOR(BST.root); } 
else
{ 
    while(BST.root->key != num)      //if the user input does not equal the root key value 
    { 
        ???? 
    }
} 

我想知道如何遍历 BST 到 BST 的节点，直到 key = num。例如，如果树有节点 3,4,5，则 TREE_SUCCESSOR(4) 应该返回 5。我该怎么做？

编辑

所以我决定使用 TREE_SEARCH(key) 找到具有特定键的节点并返回它...然后将该节点传递给 TREE_SUCCESSOR(X)。

Answer 1

按顺序执行 traversal .

找到元素后继续遍历，下一个元素就是你需要的。

如果您正在寻找根的后继者，您不需要任何特殊情况，但您需要处理元素是遍历中的最后一个元素的情况，即最大的一个。