從樹

Question

我試圖找到一個給定的樹的最大數量查找最大（Nd 3'E'E）（Nd 9'E'E））（Nd 5'E'E））（Nd 3（Nd 6'E'E） ）））0）

有人可以幫忙嗎？

謝謝！

Answer 1

因此，這裏是你的測試：

(maxi 
    (Nd 
     1 
     (Nd 2 
     (Nd 4 
      (Nd 8 'E 'E) 
      (Nd 9 'E 'E)) 
     (Nd 5 'E 'E)) 
     (Nd 3 
     (Nd 6 'E 'E) 
     (Nd 7 'E 'E))) 
    0) 

這裏是發生了什麼：

acc root what to do? 
    --------------------------------- 
    0 1  go left with acc = root 
    1 2  idem 
    2 4  idem 
    4 8  idem 
    8 E  return 8 

如果你希望你的輸入樹以滿足binary search tree性質，指出在左子樹的值總是比右側子樹的根和值都小或相等，則測試樹是畸形的BST，因爲9大於4.

By如果您有BST，那麼最大值將位於何處？

但是，如果樹只是一棵隨機樹，那麼在能夠確定總體最大值之前，必須計算兩個子樹的最大值和根值。

基本上，你想做的事：

(tree-max (Nd root left right)) = (max root 
             (tree-max left) 
             (tree-max right)) 

如果你想遞歸地做到這一點，你會遇到在基本情況下的問題，因爲你將有一個空的葉節點提供最大價值：您將選擇的任何值都會使您的代碼對包含嚴格低於該值的值的樹不正確。假設你選擇零並計算只有嚴格負數的樹的最大值，那麼零就是錯誤的答案，因爲它不出現在樹中（你能做什麼？）。

您可以選擇使用累加器而不是遞歸，但在這種情況下，您將需要兩個累加器：迄今爲止的最大值和下一個要訪問的子樹的列表。基本上你用堆分配堆棧替換調用堆棧。

我目前無法測試下面的代碼，但這裏是一個可能的實現：

(define tree-max (tree greatest todo) 
    (match tree 
    ('E greatest (if (null? todo) 
       greatest 
       (tree-max (first rest) 
          greatest 
          (rest todo)) 
    ((Nd root left right) (tree-max left 
            (max greatest root) 
            (cons right todo))))