二進制搜索樹算法

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

我剛開始使用算法，我經常看到「< - 」這個和關鍵[x]的術語可以有人告訴我關鍵是它是一個數組？ x是獲得根值，然後它被用作索引？我不明白這一點。請解釋。二進制搜索樹算法

來源

2012-11-01 Pradit

這裏的表示有點不同。 'key [x]'中的'x'不是索引。它實際上意味着「節點'x上的密鑰的值」。與'left [x]'和right [x]'類似，它們的意思是「x'的左右節點''<-'只是一個賦值語句。 – Aziz

如果您更熟悉面向對象的表示法，您可以將'key [x]'讀作'x.key'，'left [x]'將其讀作'x.left'等等 – hammar

@hammar，dont'you表示在面向對象的表示法下的C風格表示法？ – Vovanium

它是僞代碼（不是真正的語言）。

在這種情況下，<-意味着'被分配'，可以被認爲是做現代語言中的=。 key[x]是結構/對象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; 
}

來源

2012-11-01 03:45:52 James

感謝您的明確解釋。 – Pradit

這看起來像僞碼想想<-在Java中的賦值運算符=的你有時也看到的是在:=其他僞代碼變體。

x被用作指向樹中節點的指針。 key是您在繪製樹時通常在圓圈中找到的值，並且left和right是該節點的兩個孩子。

編輯：那個僞代碼也有點關閉。詹姆斯的例子很好。

來源

2012-11-01 03:48:07 rchanley

二進制搜索樹算法

回答

相關問題