Найти Максимум из дерева

Question

Я пытаюсь найти максимальное число из заданного дерева:

(define-struct (Some T) 
    ([value : T])) 

(define-type (Option T) 
    (U 'None (Some T))) 

(define-type BST (U 'E Nd)) 

(define-struct Nd 
    ([root : Integer] 
    [lsub : BST] 
    [rsub : BST])) 

(: maxi : BST Integer -> Integer) 
(define (maxi x acc) 
    (match x 
     ('E acc) 
((Nd ro ls rs) 
    (cond 
     ((> ro acc) (maxi ls ro)) 
     (else 
     (maxi rs acc)))))) 

Вышеприведенная цитата не работает должным образом, когда я ввожу следующее:

(макси (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)

Может кто-то помочь?

Спасибо!

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.

От путь, если у вас был 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))))