二分搜索树算法

Question

Search(T,k)
x<- root[T]
while x != NULL and k != key[x] 
do 
  if k<key[x]
    then x <- left[x]
  else x <- right[x]
    return x

我刚开始学习算法，我经常看到"<-“这个和keyx术语，谁能告诉我key是一个数组吗？X正在获取根值，然后将其用作索引？我不明白这一点。请解释一下。

Answer 1

它是伪代码(不是真正的语言)。

在这种情况下，<-的意思是“被赋值”，可以被认为是在做=在现代语言中所做的事情。key[x]是structure/object x的key属性的简写(这并不意味着它一定是x类的成员，它可以从数据结构(如映射)中检索。实际的实现由算法实现者决定。

所以上面的算法可以用C语言写成：

Node* Search(Tree* T, Key k)
{
    Node* x = T->Root();
    while ((x != NULL) && (k != x->Key())
    {
        if (k < x->Key())
            x = x->Left();
        else
            x = x->Right();
    }

    return x;
}

Answer 2

这看起来像psuedo-code。在Java语言中，可以将<-看作赋值操作符=。您有时还会在其他伪代码变体中看到is as :=。

x用作指向树中节点的指针。key是绘制树时通常在圆圈中找到的值，left和right是节点的两个子节点。

编辑: psuedo-code也有点问题。James的例子很好。