;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Binary Tree ADT from the book ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (define make-empty-tree (lambda () '())) (define make-nonempty-tree (lambda (root left-subtree right-subtree) (list root left-subtree right-subtree))) (define empty-tree? null?) (define root car) (define left-subtree cadr) (define right-subtree caddr) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; All else are mine ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; A useful constructor ;; Make a singleton tree (define make-singleton-tree (lambda (value) (make-nonempty-tree value (make-empty-tree) (make-empty-tree)))) ;; count the number of nodes in the binary tree "tree" (define num-nodes (lambda (tree) (if (empty-tree? tree) 0 (+ 1 (num-nodes (left-subtree tree)) (num-nodes (right-subtree tree)))))) ;; pretty-print a tree (define pretty-print (lambda (tree) (print tree 0))) (define print (lambda (tree depth) (cond ((empty-tree? tree) (newline)) (else (print (right-subtree tree) (+ 1 depth)) (print-node (root tree) depth) (print (left-subtree tree) (+ 1 depth)))))) (define print-node (lambda (value indent-level) (cond ((= indent-level 0) (display value) (newline)) (else (display " ") (print-node value (- indent-level 1)))))) ;; randomly insert the key value into tree (define random-insert (lambda (tree value) (let ((t (make-singleton-tree value))) (cond ((empty-tree? tree) t) ((= (random 2) 0) (make-nonempty-tree (root tree) (if (empty-tree? (left-subtree tree)) t (random-insert (left-subtree tree) value)) (right-subtree tree))) (else (make-nonempty-tree (root tree) (left-subtree tree) (if (empty-tree? (right-subtree tree)) t (random-insert (right-subtree tree) value)))))))) ;; Generate a random binary tree. ;; Note: The shape of the generated tree is random; the placement of keys is not. (define generate-random-tree (lambda (n) (if (= n 0) (make-empty-tree) (random-insert (generate-random-tree (- n 1)) n))))