SML - 檢查樹數據類型是否有效的函數

Question

datatype tree = br of tree*int*tree | lf 

如果左側分支的值總是低於根，而右側的分支總是更高，那麼該樹是有效的。 例如：

valid(br(br(lf,2,lf),1,lf)) = false; 
valid(br (br (lf, 2, br (lf, 7, lf)), 8, lf)) = true; 

我在尋找這樣的somethine，但我不知道如何內分支機構的整數比較根的整數。

fun valid(lf)=true 
    | valid(br(left,x,right)) = valid(left) andalso valid(right); 

編輯： 到目前爲止，我想出這個（但仍然不檢查所有的整數對所有的節點上，只需1個節點以上..它關閉，但沒有雪茄）

fun valid(lf)=true 
| valid(br(lf,x,lf)) = true 
| valid(br(lf,x,br(left2,z,right2))) = if x<z then valid(br(left2,z,right2)) else false 
| valid(br(br(left,y,right),x,lf)) = if y<x then valid(br(left,y,right)) else false 
| valid(br(br(left,y,right),x,br(left2,z,right2))) = if y<x andalso x<z then valid(br(left,y,right)) andalso valid(br(left2,z,right2)) else false; 

Answer 1

假設這是作業，我會給你一個提示，而不是一個完整的答案。這將有助於先定義一個函數，也許叫它all_nodes已鍵入

tree * (int -> bool) -> bool 

這應該是，當經過一棵樹和一個整數布爾函數返回true如果樹中的所有整數滿足功能謂詞。

然後你的函數valid應該有4個（而不是2個）子句。爲br(left,x,right)是有效的：

1）左必須有效

2）在左必須滿足它們< X中的所有整數的節點。這可以通過使用all_nodes和適當的匿名功能進行檢查

3）右必須是有效的在右

4）所有整數的節點必須> x，它再次可通過使適當的匿名函數來all_nodes被檢查

關於編輯：上述操作將會起作用，但由於對每個子樹應用兩個遞歸函數而導致一定程度的低效。另一種方法是定義一個只適用於br(left,x,right)形式的樹的輔​​助函數。這個輔助函數可以返回一個類型爲bool*int*int的元組，它告訴你樹是否有效，以及樹中的最小和最大int值。主函數將簡單地處理lf模式並調用和解釋幫助器函數。關鍵的一點是，在關鍵的遞歸步驟中，檢查節點上int的左邊和右邊的最大值就足夠了。在遞歸步驟的制定過程中需要注意一些問題，以便您不要致電lf上的幫手，但它肯定是可行的。