给定键，如何找到 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)，应该 return 5。我该怎么做？

编辑

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

Answer 1

按顺序 traversal。

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

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

Answer 2

我的第一个方法是在互联网上搜索示例 "binary search tree successor"。

但如果我有足够大的自我，我可能想开发自己的算法。我会画一个二叉搜索树。接下来，我将选择一个节点并找出到达后继节点的步骤。完成这些步骤后，我将使用树上的不同节点完成这些步骤，并根据需要调整算法（步骤）。

有了算法之后，我会把它编码出来。

但你不是我，所以你想在互联网上搜索 "c++ binary search tree successor function"。

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

How to find a certain element of BST, given key?

c++

binary-search-tree