Scheme

Thread View: pl.comp.lang.funkcyjne

2 messages

[T] Back to Threads [V] Tree View [G] Group Articles

2 total messages Started by Daniel Zet Sun, 11 Jan 2004 01:00

#552

Author: Daniel Zet
Date: Sun, 11 Jan 2004 01:00

34 lines
1837 bytes

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))
          (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ę.

-- 
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

Re: Scheme

#553

Author: Paweł 'Pasza' Ostrowski
Date: Sun, 11 Jan 2004 10:56

63 lines
2953 bytes

"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

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads