🚀 go-pugleaf

"Daniel Zet" <ldexp@gazeta.SKASUJ-TO.pl> writes:

> Mam prośbę. Oto program w języku scheme budujący drzewo binarne z
> uporzadkowanymi elementami tzn po lewej stronie(lewe poddrzewo) sa liczby
> mniejsze od korzenia po prawej wieksze.
>
>
>
> (define (build-tree l)
>
>    (build-tree1 l '()))
>
> (define (build-tree1 l t)
>    (if(null? l)
>      t
>      (build-tree1 (cdr l) (insert-tree(car l) t))))
>
> (define(insert-tree d t)
>    (if(null? t)
>     (build-node d '() '())
>     (if (< d (node t))
>        (build-node(node t) (insert-tree d (l-tree t)) (r-tree t))
>        (if (> d(node t))

               ^^^^^
Tu ma być spacja. Czyli (> d (node t))

>           (build-node(node t) (l-tree t)(insert-tree d (r-tree t)))
>           (build-node(node t) (insert-tree d (l-tree t))(r-tree t ))))))
> (define (build-node d l1 l2)
>       (list d l1 l2))
>
> czy ktoś może mi pomóc albo dać jakąś wskazówkę jak przerobić taki program
> by sprawdzał on czy już istniejące drzewo binarne ma w węzłach liczby
> całkowite i czy jest uporządkowany (po lewej mniejsze itd)
>  z góry dziękuję.

Nie znam scheme, ale piszę w common lispie. Program, który zamieściłeś
nie jest kompletny. Brakuje funkcji node, l-tree i r-tree (chyba, że
nie zamieściłeś bo są oczywiste, wtedy wskazówka 1 odpada).

1) Jeśli to ma działać, to proponuję zacząć od uzupełnienia programu
powyżej.

(define (node t)
  (car t))

Do napisanie zostają l-tree, r-tree.

2) Bardziej dotyczy tego o co pytałeś: poczytaj o drzewach bst. Musisz
zobaczyć czy lewy węzeł jest mniejszy, lewe poddrzewo dobre, prawy
węzeł większy, prawe poddrzewo dobre.

   Inny sposób (a właściwie ten sam), przejść infiksowo po drzewie
wrzucając wierzchołki do listy. Powinienneś otrzymać listę
posortowaną (to już łatwo jest sprawdzić).

Jak już będziesz umiał chodzić po drzewach :), to pewnie poradzisz
sobie z tymi liczbami całkowitymi.

-- 
Pasza - (format t "~36R!~%" 1807251954038279265358)
pasza (at) zodiac.mimuw.edu.pl