Copyright © 2005 Suradet Jitprapaikulsarn
สงวนลิขสิทธิ์ 2548 สุรเดช จิตประไพกุลศาล

Homework 8 (Due 15 August 2005)

  1. Write a function, nNode, to determine the number of nodes in a ternary tree.  Solution.
;------------------------------------------------------------------------------
; @description calculate the number of nodes in a ternary tree
; @param T a ternary tree
; @return the number of nodes in a ternary tree
; @contract nNode: TT -> number
; @example (nNode empty) = 0
; @example (nNode tree-1) = 1
; @example (nNode tree-2) = 1
; @example (nNode tree-3) = 1
; @example (nNode tree-4) = 4
;------------------------------------------------------------------------------
(define (nNode T)
  (cond
    [(empty? T) 0]
    [else (+ 1
             (nNode (TT-left T))
             (nNode (TT-middle T))
             (nNode (TT-right T))) ] ) )
  1. Write a function, count, to determine the number of occurrences of a number in a ternary tree.
;------------------------------------------------------------------------------
; @description determine the number of occurrences of a number in a ternary tree
; @param num the number to look for
; @param T a ternary tree
; @return the number of occurrences of a number in a ternary tree
; @contract count: number TT -> number
; @example (count 1 empty)  = 0
; @example (count 1 tree-1) = 1
; @example (count 2 tree-2) = 2
; @example (count 2 tree-3) = 0
; @example (count 2 tree-4) = 1
;------------------------------------------------------------------------------
(define (count num T)
  (cond
    [(empty? T) 0]
    [(eq? (TT-data T) num) (+ 1
                              (count num (TT-left T))
                              (count num (TT-middle T))
                              (count num (TT-right T)) ) ]
    [else (+ (count num (TT-left T))
             (count num (TT-middle T))
             (count num (TT-right T))) ] ) )
  1. Write a function, replace, to replace a number in a ternary tree with another number.
;------------------------------------------------------------------------------
; @description replace every occurrence of a number in a ternary tree with
;              another number
; @param T a ternary tree
; @param old the replaced number
; @param new the replacing number
; @return a new ternary with every occurrence of old is replaced by new
; @contract replace: TT number number -> TT
; @example (replace empty 1 5) = empty
; @example (replace tree-1 1 5) = (make-TT 5 empty empty empty)
; @example (replace tree-2 1 5) = (make-TT 2 empty empty empty)
; @example (replace tree-3 1 5) = (make-TT 3 empty empty empty)
; @example (replace tree-4 1 5) = (make-TT 4
;                                          (make-TT 5 empty empty empty)
;                                          (make-TT 2 empty empty empty)
;                                          (make-TT 3 empty empty empty))
;------------------------------------------------------------------------------
(define (replace T old new)
  (cond
    [(empty? T) empty]
    [(eq? (TT-data T) old) (make-TT new
                                    (replace (TT-left T) old new)
                                    (replace (TT-middle T) old new)
                                    (replace (TT-right T) old new))]
    [else (make-TT (TT-data T)
                   (replace (TT-left T) old new)
                   (replace (TT-middle T) old new)
                   (replace (TT-right T) old new)) ] ) )
  1. Write a function, range, to determine the range of numbers in a ternary tree (the difference between the maxinum and the minimum values)
;------------------------------------------------------------------------------
; @description determine the maximum value in a ternary tree
; @param T a ternary tree
; @return 'Error if the T is empty, otherwise the maximum of a ternary tree
; @contract maxValue: TT -> number or 'Error
; @example (maxValue empty) = 'Error
; @example (maxValue tree-1) = 1
; @example (maxValue tree-2) = 2
; @example (maxValue tree-3) = 3
; @example (maxValue tree-4) = 4
;------------------------------------------------------------------------------
(define (maxValue T)
  (cond
    [(empty? T) 'Error]
    [(and (empty? (TT-left T))
          (empty? (TT-middle T))
          (empty? (TT-right T))) (TT-data T)]
    [(and (empty? (TT-middle T))
          (empty? (TT-right T))) (max2 (TT-data T)
                                       (maxValue (TT-left T)))]
    [(and (empty? (TT-left T))
          (empty? (TT-middle T))) (max2 (TT-data T)
                                        (maxValue (TT-right T)))]
    [(and (empty? (TT-left T))
          (empty? (TT-right T))) (max2 (TT-data T)
                                       (maxValue (TT-middle T)))]
    [(empty? (TT-left T)) (max2 (TT-data T)
                                (max2 (maxValue (TT-middle T))
                                      (maxValue (TT-right T))))]
    [(empty? (TT-middle T)) (max2 (TT-data T)
                                  (max2 (maxValue (TT-left T))
                                        (maxValue (TT-right T))))]
    [(empty? (TT-right T)) (max2 (TT-data T)
                                 (max2 (maxValue (TT-left T))
                                       (maxValue (TT-middle T))))]
    [else (max2 (TT-data T)
                (max2 (maxValue (TT-left T))
                      (max2 (maxValue (TT-middle T))
                            (maxValue (TT-left T)))))]))


;------------------------------------------------------------------------------
; @description determine the minimum value in a ternary tree
; @param T a ternary tree
; @return 'Error if the T is empty, otherwise the minimum of a ternary tree
; @contract minValue: TT -> number or 'Error
; @example (minValue empty) = 'Error
; @example (minValue tree-1) = 1
; @example (minValue tree-2) = 2
; @example (minValue tree-3) = 3
; @example (minValue tree-4) = 4
;------------------------------------------------------------------------------
(define (minValue T)
  (cond
    [(empty? T) 'Error]
    [(and (empty? (TT-left T))
          (empty? (TT-middle T))
          (empty? (TT-right T))) (TT-data T)]
    [(and (empty? (TT-middle T))
          (empty? (TT-right T))) (min2 (TT-data T)
                                       (minValue (TT-left T)))]
    [(and (empty? (TT-left T))
          (empty? (TT-middle T))) (min2 (TT-data T)
                                        (minValue (TT-right T)))]
    [(and (empty? (TT-left T))
          (empty? (TT-right T))) (min2 (TT-data T)
                                       (minValue (TT-middle T)))]
    [(empty? (TT-left T)) (min2 (TT-data T)
                                (min2 (minValue (TT-middle T))
                                      (minValue (TT-right T))))]
    [(empty? (TT-middle T)) (min2 (TT-data T)
                                  (min2 (minValue (TT-left T))
                                        (minValue (TT-right T))))]
    [(empty? (TT-right T)) (min2 (TT-data T)
                                 (min2 (minValue (TT-left T))
                                       (minValue (TT-middle T))))]
    [else (min2 (TT-data T)
                (min2 (minValue (TT-left T))
                      (min2 (minValue (TT-middle T))
                            (minValue (TT-left T)))))]))


;------------------------------------------------------------------------------
; @description determine the range of values in a ternary tree
; @param T a ternary tree
; @return the difference of the largest and the smallest numbers in a ternary tree
; @contract range: TT -> number
; @example (range empty) = 0
; @example (range tree-1) = 0
; @example (range tree-2) = 0
; @example (range tree-3) = 0
; @example (range tree-4) = 3
;------------------------------------------------------------------------------
(define (range T)
  (cond
    [(empty? T) 0]
    [else (- (maxValue T)
             (minValue T))]))
  1. (Bonus) Write a function, strictlyBT?, to determine whether a binary tree is a strictly binary tree.  A strictly binary tree has the following properties: Solution.
;------------------------------------------------------------------------------
; @description determine whether a binary tree is a strictly binary tree
; @note a strictly binary search tree is a binary tree such that every node
;       either is a leaf or has precisely two children
; @param T a binary tree
; @return true if a binary tree is a strictly binary tree
; @contract strictlyBT?: BT -> boolean
; @example (strictlyBT? empty) = true
; @example (strictlyBT? tree-1) = true
; @example (strictlyBT? tree-2) = false
; @example (strictlyBT? tree-3) = false
; @example (strictlyBT? tree-4) = false
; @example (strictlyBT? tree-5) = false
; @example (strictlyBT? tree-6) = false
; @example (strictlyBT? tree-7) = true
; @example (strictlyBT? tree-8) = false
; @example (strictlyBT? tree-9) = true
; @example (strictlyBT? tree-10) = true
; @example (strictlyBT? tree-11) = true
; @example (strictlyBT? tree-12) = true
; @example (strictlyBT? tree-13) = true
; @example (strictlyBT? tree-14) = true
; @example (strictlyBT? tree-15) = true
; @example (strictlyBT? tree-16) = true
; @example (strictlyBT? tree-17) = true
; @example (strictlyBT? tree-18) = true
; @example (strictlyBT? tree-19) = true
; @example (strictlyBT? tree-20) = true
;------------------------------------------------------------------------------
(define (strictlyBT? T)
  (cond
    [(empty? T) true]
    [(and (empty? (BT-left T)) (empty? (BT-right T))) true]
    [else (and (not (empty? (BT-left T)))
               (not (empty? (BT-right T)))
               (strictlyBT? (BT-left T))
               (strictlyBT? (BT-right T)))]))