[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) ```