查找AVL樹

我現在已經建立了一個AVL樹第k個分節點，這裏是一個函數來找到第k個分節點AVL樹（K從0開始）代碼：查找AVL樹

int kthMin(int k) 
{ 
    int input=k+1; 
    int count=0; 
    return KthElement(root,count,input); 
} 

int KthElement(IAVLTreeNode * root, int count, int k) 
{ 
    if(root) 
    { 
     KthElement(root->getLeft(), count,k); 
     count ++; 
     if(count == k) 
      return root->getKey(); 
     KthElement(root->getRight(),count,k); 
    } 
    return NULL; 
}

它可以找到一些正確的節點，但有些可能會失敗，任何人都可以幫助我調試此問題> THanks

來源

2013-11-21 user2840454

從左側遞歸後，count將爲1，無論左側有多少個節點。

您需要在遞歸調用中更改count，因此請將count更改爲通過引用傳遞（假設這是C++）。

int KthElement(IAVLTreeNode * root, int &count, int k)

（我不認爲需要通過其他代碼更改來通過參考工作在這裏）。

及以後，你需要實際返回的遞歸調用生成的值，即改變：

KthElement(root->getLeft(), count, k);

到：

int val = KthElement(root->getLeft(), count, k); 
if (val != 0) 
    return val;

，類似的還有getRight。

注意我使用0而不是NULL。 NULL通常用於指空指針，並將其轉換爲0int（後者在使用int時首選）。

這當然假定0不是樹中的有效節點（否則你的代碼將無法工作）。如果是，則需要找到另一個要使用的值或指向該節點的指針（在這種情況下，您可以使用NULL來指示未找到）。

來源

2013-11-21 14:17:29 Dukeling

Hi Duke，感謝您的建議，我現在發現了這個bug，似乎在一些遞歸調用之後，最終的返回值總是最後一行「return NULL」。我現在在行下使用了一個私有變量「int kth」if（count == k）kth = root-> getKey（）;然後在第一個Kthmin函數中返回第k個。然後問題解決了。 – user2840454

這裏是第K最小的節點簡單的算法，一般所有的樹： -

count=0, found=false; 

kthElement(Node p,int k) { 

    if(p==NULL) 
     return -1 

    else { 

     value = kthElement(p.left)    
     if(found) 
      return value 

     count++ 
     if(count==k) { 
      found = true 
      return p.value 
     } 

     value = kthElement(p.right) 
     return value 
    } 
}

注： -使用全局變量是關鍵。

來源

2013-11-21 16:16:44

回答

相關問題