======P10.scm====== <code shell>#!/usr/bin/env racket #lang racket/base</code> přiklady, programy, kód z [[PAPR1:L10|Lekce 10]] * n-ární a binární stromy 10.1, 10.3 * množiny jako uspořádané seznamy 10.2, nebo BST: 10.3 * kombinatorika 10.4 ======= 10.1 n-ární stromy ======= a /|\ b c d |\ e f /|\ g h i | j <code scheme> (define tree-aj '(a (b) (c (e) (f (g) (h) (i (j)))) (d)) ) </code> <hidden tree konstruktory a accessory> <code scheme> (define tree (lambda (val . subtrees) (cons val subtrees))) (define get-val car) (define (get-branches tree) (if (null? tree) '() (cdr tree));safe-cdr ) </code> </hidden> (a (b c) (...)) <hidden je to seznam, mimo prvního seznamy?> <code scheme> (define (forall p? l) (or (null? l);prazdna mnozina splnuje (and (p? (car l)) (forall p? (cdr l))))) (define (tree? t) (and (list? t) (forall tree? (cdr t)))) ; ;stejne jako tree?, ale forall inline named let: (define (tree2? t) (and (list? t) (let forall ((p? tree?) (l (cdr t))) (or (null? l) (and (p? (car l)) (forall p? (cdr l)))));inline forall, named-let iterace )) </code> </hidden> <code scheme> (map tree? (list tree-aj 1 '(1 . 2) '(1 2) '(1 (2 3)) '(1 (2 (3))) )) (map tree2? (list tree-aj 1 '(1 . 2) '(1 2) '(1 (2 3)) '(1 (2 (3))) )) </code> <hidden levá a pravá větev> <code scheme> (define (left-branches tree k) (if (or (< k 0) (null? tree)) '() (let iter ((k k) (branches (cdr tree))) (cond ((null? branches) '()) ((= k 0) (car branches)) (else (iter (- k 1) (cdr branches))))))) (define (right-branches tree k) (left-branches tree (- (length tree) k -2))) </code> </hidden> <code scheme> (map (lambda (k) (left-branches tree-aj k)) '(0 1 2 3 4)) (map (lambda (k) (left-branches '(r (a) (b) (c) (d)) k)) '(0 1 2 3 4)) </code> <hidden deep-first-search> <code scheme> (define (dfs tree) (if (null? tree) '() (cons (get-val tree) ;( dfs (get-branches tree)) ;mapuj dfs na branches => apply append (apply append (map dfs (get-branches tree))) ))) </code> </hidden> <code scheme> (dfs tree-aj) (equal? (dfs tree-aj) '(a b c e f g h i j d)) </code> do sirky: iterace po patrech: <code> (a (b) (c (f))) (d ...) (e ...)) </code> <hidden breath-firts-search> <code scheme> (define (bfs tree) (let patro ((tree (list tree)));"pridame" patro navic (display tree) (newline) (if (null? tree) '() (append (map get-val tree);hodnoty tohoto patra ;rekurze do dalsiho patra (patro (apply append (map get-branches tree))))))) </code> </hidden> <code scheme> '(bfs testy) tree-aj (map (lambda (x) (display `(x: ,x)) (newline)) tree-aj) </code> (map get-val tree-aj) ;nefunguje!!! <code scheme> (map get-val (list tree-aj)) (map get-val (get-branches tree-aj)) `(bfs: ,(bfs tree-aj)) `(dfs: ,(dfs tree-aj)) </code> ======= 10.3 BST, reprezentace množin ======= BST: prázdný nebo strom s dvěma podtromy <hidden BST konstruktory a selektory> <code scheme> (define (make-bst val left right) (list val left right)) (define (make-leaf val) (make-bst val '() '())) (define (bst-val tree) (car tree)) (define (bst-left tree) (cadr tree)) (define (bst-right tree) (caddr tree)) </code> /<hidden> <code scheme> (define bstree (make-bst 4 (make-bst 2 (make-leaf 1) (make-leaf 3)) (make-bst 6 (make-leaf 5) (make-leaf 7)))) bstree </code> * union a inter: sjednocení a průnik predikát in * prazdný => #f * hodnota rovna => #t * jinak left/right podle <= <hidden predikát in? pro BST> <code scheme> (define (bst-in? x tree) (cond ((null? tree) #f) ((= x (bst-val tree)) #t) ((< x (bst-val tree)) (bst-in? x (bst-left tree))) (else (bst-in? x (bst-right tree))))) </code> </hidden> <code scheme> (let ((cisla '(1 2 3 4 5 6 7 99))) (map cons cisla (map (lambda (x) (bst-in? x bstree)) cisla))) </code> <hidden konstruktor cons-bst: přidá prvek do množiny> <code scheme> (define (cons-bst x tree) </code> (display `(x: ,x tree: ,tree)) (newline) <code scheme> (cond ((null? tree) (make-leaf x));vratime novy leaf ((= x (bst-val tree)) tree) ;roven/nasli, vratime ((< x (bst-val tree)) (make-bst (bst-val tree) (cons-bst x (bst-left tree)) (bst-right tree))) (else (make-bst (bst-val tree) (bst-left tree) (cons-bst x (bst-right tree)))))) </code> </hidden> <code scheme> (cons-bst 1 '()) (cons-bst 2 (cons-bst 1 '())) (let iter ((i 1) (tree '())) (if (> i 10) tree (iter (+ i 1) (cons-bst i tree)))) ;nebude balancovany!? </code> Program 10.x <hidden xxx> </hidden> <code scheme> ; vim: syntax=racket </code>