[TOC] ## 概述  ### BT 二叉树 binary-tree (简称 BT) 是下列两者之一 1. false 2. (make-node soc pn lft rgt) 其中 soc 是数, pn 是符号 ,lft 与 rgt 是 bt ### BST 二插搜索树(带排序的二叉树) 二插搜索树(binary-search-tree,简称 BST) 是 BT 1. false 总是 BST 2. (make-node soc pn lft rgt) 是 BST 如果 a. lft 和 rgt 是 BST b. lft 中所有的 ssn 数都比 soc 小 c. rgt 中所有的 ssb 数都比 soc 大 ## 14.2.1 二叉树查数 按照图144的方法,给出上述的两棵树的形象表示。然后开发 contains-bt,该函数读入一个数和一棵BT,判断这个数是否在树中出现。 ``` ;; 判断数是否在二叉树中 ;; node 定义 (define-struct node (soc pn lft rgt)) ;; contains-bt:number,bt->boolean ;; 15,node1->true ;; 13,node2->false (define (contains-bt n bt) (cond [(= n (node-soc bt)) true] [(node? (node-rgt bt)) (contains-bt n (node-rgt bt))] [(node? (node-lft bt)) (contains-bt n (node-lft bt))] [else false])) (define node1 (make-node 15 'd false (make-node 24 'i false false))) (define node2 (make-node 15 'd (make-node 87 'h false false) false)) ;(contains-bt 15 node1) ; #true ;(contains-bt 24 node1) ; #true ;(contains-bt 23 node1) ; #false (contains-bt 87 node2) ; #true ``` ## 14.2.2 二叉树通过数查找symbol 开发 search-bt,该函数读入数n和一棵BT。如果这棵树中包含一个node,其soc字段值为n,函数就返回这个节点的pn字段的值;否则,函数返回 false ``` ;; 判断数soc是否在二叉树中,存在则返回 pn ;; node 定义 (define-struct node (soc pn lft rgt)) ;; contains-bt:number,bt->boolean ;; 15,node1->pn ;; 13,node2->false (define (contains-bt n bt) (cond [(= n (node-soc bt)) (node-pn bt)] [(node? (node-rgt bt)) (contains-bt n (node-rgt bt))] [(node? (node-lft bt)) (contains-bt n (node-lft bt))] [else false])) (define node1 (make-node 15 'd false (make-node 24 'i false false))) (define node2 (make-node 15 'd (make-node 87 'h false false) false)) ;(contains-bt 87 node2) ; 'h (contains-bt 88 node2) ; #false ``` ## 14.2.2 二插搜索树 查找值 search-bt,该函数读入数n和一棵BT。如果这棵树中包含一个node,其soc字段值为n,函数就返回这个节点的pn字段的值;否则,函数返回 false ``` ;; 判断数soc是否在二叉搜索树中,存在则返回 pn ;; node 定义 (define-struct node (soc pn lft rgt)) ;; contains-bst:number,bst->boolean | pn ;; 15,node1->pn ;; 13,node2->false (define (search-bst n bst) (cond [(node? bst) (cond [(= n (node-soc bst)) (node-pn bst)] [(> n (node-soc bst)) (search-bst n (node-rgt bst)) ] [(< n (node-soc bst)) (search-bst n (node-lft bst)) ]) ] [else false])) (define node1 (make-node 15 'd (make-node 9 'k false false) (make-node 24 'i false false))) ;(search-bst 25 node1 );false ;(search-bst 8 node1 );false (search-bst 9 node1 );'k (search-bst 24 node1 );'i ``` ## 14.3 表中的表 教程案例, 计算网页中单词个数 ``` ;; szie : wp ->number ;; 案例 ;; (= (size empty) 0) ;; (= (size (cons 'One empty)) 1) ;; (= (size (cons (cons 'One empty) empty)) 1) ;; 当 cons 第一个元素是非empty时,返回为一 ;; 模版 ;;第二和第三个 cond 子句中包含了表的第一个元素和其余部分的选择器表达 ;;式。因为(rest a-wp)总是网页,而在第三个子句中,(first a-wp)也是网页,所以我们还为这些选择器表达式 ;;加上 size 的递归调用 ;;(define (size a-wp) ;; (cond ;; [(empty? a-wp) 0] ;; [(symbol? (first a-wp)) ... (first a-wp) .. (size (rest a-wp))] ;; [else ... (size (first a-wp)) ... (size (rest a-wp)])) (define (size a-wp) (cond [(empty? a-wp) 0] [(symbol? (first a-wp)) (+ 1 (size (rest a-wp)))] [else (+ (size (first a-wp)) (size (rest a-wp)))])) (= (size empty) 0) (= (size (cons 'One empty)) 1) (= (size (cons (cons 'One empty) empty)) 1) (= (size (list 'a 'b 'c (list 'z 'e))) 5) ``` ## 14.3.2 字符出现次数 开发函数 occurs1，该函数读入一个网页和一个符号，返回该符号在网页中出现的次数，忽略 嵌入的网页 ``` ;; occurs1 : sym,wp->number ;; 读入一个网页和一个符号,返回该符号在网页中出现的次数,忽略嵌入的网页 ;; 解析,如果元素为表就跳过, ;; 例子 ;;(= (occurs1 'a empty) 0) ;;(= (occurs1 'a (list 'a)) 1) ;;(= (occurs1 'a (list 'a (list 'a))) 1) ;;(= (occurs1 'a (list 'b 'a)) 1) ;; 模版 ;;(define (occurs1 sym wp) ;; (cond ;; [(empty? wp) ...] ;; [(cons? (first wp)) ...] ;; [(eq? sym (fits wp)) ... (first wp) ... (occurs1 sym (rest wp))] ;; [else ...(occurs1 sym (rest wp))...])) (define (occurs1 sym wp) (cond [(empty? wp) 0] [(cons? (first wp)) 0] [(eq? sym (first wp)) (+ 1 (occurs1 sym (rest wp)))] [else (occurs1 sym (rest wp))])) ;;测试 (= (occurs1 'a empty) 0) (= (occurs1 'a (list 'a)) 1) (= (occurs1 'a (list 'a (list 'a))) 1) (= (occurs1 'a (list 'b 'a)) 1) ``` ## 14.3.3 字符替换 该函数读入符号 new 和 old,以及网页 a-wp,返回一个网页,该网页在结 构上和 a-wp 相同，但其中所有 old 的出现都被替换成 new ``` ;; occurs2 : new,old,wp->wp ;; 该函数读入符号 new 和 old,以及网页 a-wp,返回一个网页,该网页在结 ;; 构上和 a-wp 相同，但其中所有 old 的出现都被替换成 new ;; 例子 ;;(replace 'a 'b empty) ;'() ;;(replace 'a 'b (list 'b )) ; (cons 'a '()) ;;(replace 'a 'b (list 'b (list 'b) )) ; (cons 'a (cons (cons 'a '()) '())) ;;(replace 'a 'b (list 'b 'c )) ; (cons 'a (cons 'c '())) ;; 模版 ;;(define (replace new old wp) ;; (cond ;; [(empty? wp) ...] ;; [(cons? (first wp)) ... (replace new old (first wp)) ... (replace new old (rest wp)) ...] ;; [(eq? old (first wp)) ... new ... ((replace new old(rest wp))) ...] ;; [else ... (first wp) ... (replace new old (rest wp)) ...)])) (define (replace new old wp) (cond [(empty? wp) empty] [(cons? (first wp)) (cons (replace new old (first wp)) (replace new old (rest wp)) )] [(eq? old (first wp)) (cons new (replace new old (rest wp)))] [else (cons (first wp) (replace new old (rest wp)) )])) ;;测试 (replace 'a 'b empty) (replace 'a 'b (list 'b )) (replace 'a 'b (list 'b (list 'b) )) (replace 'a 'b (list 'b 'c )) ``` ## 14.3.4 获取最深嵌入页网页深度 ``` ;; depth : wp->number ;; 获取最深嵌入页网页深度 ;; 例子 ;;(= (depth empty) 0) ;;(= (depth (list 'a)) 1) ;;(= (depth (list 'a (list 'a))) 2) ;;(= (depth (list 'a (list 'a 'a) (list 'a 'a 'a))) 4) ;; 模版 ;;(define (depth wp) ;; (cond ;; [(empty? wp ) ...] ;; [(symbol? (first wp)) ... (first wp) ... (depth (rest wp)) ...] ;; [(cons? (first wp )) (cond ;; [(> (depth (first wp)) (depth (rest wp))) (depth (first wp))] ;; [else (depth (rest wp))])])) (define (depth wp) (cond [(empty? wp ) 0] [(symbol? (first wp)) (+ 1 (depth (rest wp)))] [(cons? (first wp )) (cond [(> (depth (first wp)) (depth (rest wp))) (depth (first wp))] [else (depth (rest wp))])])) ;;测试 (= (depth empty) 0) (= (depth (list 'a)) 1) (= (depth (list 'a (list 'a))) 2) (= (depth (list 'a (list 'a 'a) (list 'a 'a 'a))) 4) ```