檢查樹是否爲BST

我在ruby中編寫了一個代碼來檢查樹是否是二叉搜索樹。只是想檢查我是否在正確的軌道上。檢查樹是否爲BST

def checkBST(t) 
    return false if t==nil 
    if t.left!=nil && t.left>t 
     return false 
    end 
    if t.right!=nil && t.right<t 
     return false 
    end 
    if checkBST(t.left) && checkBST(t.right) 
     return true 
    end 
end

來源

2016-11-29 Clement

誰說空樹（'噸== nil'）不是一個有效的BST？你的基本情況對我來說似乎不正確。此外，現在這個問題需要詳細闡述。代碼中的當前_issue_是什麼？請明確點。檢查出[ask] – CollinD

我的意思是，這段代碼是檢查樹（它的值）是否像BST一樣排列。我不太確定我的代碼是否按照我想要的方式工作，我想獲得更多意見，也許如何使它更有效率或什麼？ – Clement

SO不是代碼測試服務。你完全有能力運行它，看看它是否可以自己工作。確保檢查像多個相同的鍵和空樹的邊緣情況。如果它不起作用，它會給出不好的輸出或崩潰，而不會破壞宇宙。不要害怕運行你的代碼，只是看看它是否工作。如果你正在尋找代碼審查，那麼還有另一個SE網站。如果你有一個特定的問題，那就是這個地方。如果您對問題有更新或澄清，最好將其作爲對問題的修改而不是評論發佈。 – CollinD

讓我行第一行解釋： -

1 def checkBST(t) 
2  return false if t==nil 
3  if t.left!=nil && t.left>t 
4   return false 
5  end 
6  if t.right!=nil && t.right<t 
7   return false 
8  end 
9  if checkBST(t.left) && checkBST(t.right) 
10   return true 
11  end 
12 end

2號線 - 當t爲NULL返回true。

第3行和第6行 - 您是否正在檢查直系孩子，如果孩子滿足BST財產而不是其大孩子，該怎麼辦？試試自己，你會知道我想說什麼。

這裏是一個可能的解決方案 - 我只是寫它，沒有編譯，你可以更多的工作。

功能 -

bool isBST(class tree* root, int minL, int maxR) 
{ 
    if(!root) 
     return true; 
    else if(root->data > minL && root->data < maxR) 
     return true; 
    else if(root->data < minL || root->data > maxR) 
     return false; 
    return isBST(root->right, root->data, maxR) && isBST(root->left, minL, root->data); 
} 

Caller - 
isBST(root, INT_MIN, INT_MAX);

來源

2016-11-30 13:48:02 instance

檢查樹是否爲BST

回答

相關問題