Blame


1 12687dd9 2023-08-04 jrmu ;; The first three lines of this file were inserted by DrScheme. They record metadata
2 12687dd9 2023-08-04 jrmu ;; about the language level of this file in a form that our tools can easily process.
3 12687dd9 2023-08-04 jrmu #reader(lib "htdp-advanced-reader.ss" "lang")((modname |31.3|) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #t #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp")))))
4 12687dd9 2023-08-04 jrmu (define-struct node (left right))
5 12687dd9 2023-08-04 jrmu
6 12687dd9 2023-08-04 jrmu ;A binary-tree (bt) is either
7 12687dd9 2023-08-04 jrmu ;1. empty or
8 12687dd9 2023-08-04 jrmu ;2. (make-node l r)
9 12687dd9 2023-08-04 jrmu ;where l,r are binary-trees (bt).
10 12687dd9 2023-08-04 jrmu ;
11 12687dd9 2023-08-04 jrmu ;height-1 : bt -> number
12 12687dd9 2023-08-04 jrmu ;Determines the height (depth) of a binary tree using structural recursion.
13 12687dd9 2023-08-04 jrmu
14 12687dd9 2023-08-04 jrmu (define (height-1 abt)
15 12687dd9 2023-08-04 jrmu (cond
16 12687dd9 2023-08-04 jrmu [(empty? abt) 0]
17 12687dd9 2023-08-04 jrmu [else (+ (max (height-1 (node-left abt))
18 12687dd9 2023-08-04 jrmu (height-1 (node-right abt)))
19 12687dd9 2023-08-04 jrmu 1)]))
20 12687dd9 2023-08-04 jrmu
21 12687dd9 2023-08-04 jrmu ;height-2 : bt -> number
22 12687dd9 2023-08-04 jrmu ;Determines the height (depth) of a binary tree using an accumulator.
23 12687dd9 2023-08-04 jrmu
24 12687dd9 2023-08-04 jrmu (define (height-2 abt)
25 12687dd9 2023-08-04 jrmu (local ;; the accumulator represents the number of nodes passed in going from abt to bt0
26 12687dd9 2023-08-04 jrmu ((define (height-aux bt0 accumulator)
27 12687dd9 2023-08-04 jrmu (cond
28 12687dd9 2023-08-04 jrmu [(empty? bt0) accumulator]
29 12687dd9 2023-08-04 jrmu [else (max (height-aux (node-left bt0) (+ 1 accumulator))
30 12687dd9 2023-08-04 jrmu (height-aux (node-right bt0) (+ 1 accumulator)))])))
31 12687dd9 2023-08-04 jrmu (height-aux abt 0)))
32 12687dd9 2023-08-04 jrmu
33 12687dd9 2023-08-04 jrmu (define bt1 (make-node
34 12687dd9 2023-08-04 jrmu (make-node
35 12687dd9 2023-08-04 jrmu empty
36 12687dd9 2023-08-04 jrmu (make-node empty empty))
37 12687dd9 2023-08-04 jrmu empty))
38 12687dd9 2023-08-04 jrmu (height-1 bt1)
39 12687dd9 2023-08-04 jrmu (height-2 bt1)