Copyright ©
2005 Suradet Jitprapaikulsarn
สงวนลิขสิทธิ์ 2548 สุรเดช จิตประไพกุลศาล
Homework 7 (Due 8 August 2005)
- Write a function, height, to determine the height of a binary tree. Solution.
;------------------------------------------------------------------------------
; @description calculate the height of a binary tree
; @param T a binary tree
; @return the height of a binary tree
; @contract height: BT -> number
; @example (height empty) = 0
; @example (height tree-1) = 1
; @example (height tree-2) = 2
; @example (height tree-3) = 3
; @example (height tree-4) = 4
; @example (height tree-5) = 3
; @example (height tree-6) = 2
; @example (height tree-7) = 1
;------------------------------------------------------------------------------
(define (height T)
(cond
[(empty? T) 0]
[else (+ 1 (max2 (height (BT-left T))
(height (BT-right T)))) ] ) )
- Write a function, maxValue, to determine the maximum value in a binary tree of numbers. Be careful about an empty tree.
;------------------------------------------------------------------------------
; @description determine the maximum value in a binary tree
; @param T a binary tree
; @return 'Error if the T is empty, otherwise the maximum of a binary tree
; @contract maxValue: BT -> 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) = 7
; @example (maxValue tree-5) = 7
; @example (maxValue tree-6) = 7
; @example (maxValue tree-7) = 7
;------------------------------------------------------------------------------
(define (maxValue T)
(cond
[(empty? T) 'Error]
[(and (empty? (BT-left T)) (empty? (BT-right T))) (BT-data T)]
[(empty? (BT-left T)) (max2 (BT-data T)
(maxValue (BT-right T)))]
[(empty? (BT-right T)) (max2 (BT-data T)
(maxValue (BT-left T)))]
[else (max2 (BT-data T)
(max2 (maxValue (BT-right T))
(maxValue (BT-left T))))]))
- Write a function, BST?, to determine whether a binary tree is a binary search tree (BST). A BST is a binary tree with the following properties:
- For each node in a BST:
- all the values in the left subtree are less than the value in the node
- all the values in the right subtree are more than the value in the node
;------------------------------------------------------------------------------
; @description determine whether a binary tree is a binary search tree
; @note a binary search tree is a binary tree such that
; - every value on the left branch is less than the value of the
; current node
; - every value on the right branch is greater than the value of the
; current node
; @remark In order that every value on the left branch is less than the value
; of the current node, the maximum value of the left branch must be less
; than the value of the current node. Similarly, if the minimum value of
; right branch is greater than the value of the current node, every value
; on the right branch must be greater than the value of the current node.
; @param T a binary tree
; @return true if a binary tree is a binary search tree
; @contract BST?: BT -> boolean
; @example (BST? empty) = true
; @example (BST? tree-1) = true
; @example (BST? tree-2) = true
; @example (BST? tree-3) = true
; @example (BST? tree-4) = true
; @example (BST? tree-5) = true
; @example (BST? tree-6) = true
; @example (BST? tree-7) = true
; @example (BST? tree-8) = true
; @example (BST? tree-9) = true
; @example (BST? tree-10) = true
; @example (BST? tree-11) = true
; @example (BST? tree-12) = true
; @example (BST? tree-13) = false
; @example (BST? tree-14) = true
; @example (BST? tree-15) = true
; @example (BST? tree-16) = true
; @example (BST? tree-17) = true
; @example (BST? tree-18) = false
; @example (BST? tree-19) = true
; @example (BST? tree-20) = true
;------------------------------------------------------------------------------
(define (BST? T)
(cond
[(empty? T) true]
[(and (empty? (BT-left T)) (empty? (BT-right T))) true]
[(empty? (BT-left T)) (and (< (BT-data T) (minValue (BT-right T)))
(BST? (BT-right T)))]
[(empty? (BT-right T)) (and (> (BT-data T) (minValue (BT-left T)))
(BST? (BT-left T)))]
[else (and (< (BT-data T) (minValue (BT-right T)))
(> (BT-data T) (minValue (BT-left T)))
(BST? (BT-right T))
(BST? (BT-left T)) ) ] ) )
- (Bonus) Write a function, longestDistance,
to determine the longest distance between two nodes in a binary tree.
Note that the longest path does not need to include the root of
the tree.
;------------------------------------------------------------------------------
; @description determine the number of nodes on the longest path in a binary tree
; @param T a binary tree
; @return the number of nodes on the longest path
; @contract longestDistance: BT -> number
; @example (longestDistance empty) = 0
; @example (longestDistance tree-1) = 1
; @example (longestDistance tree-2) = 2
; @example (longestDistance tree-3) = 3
; @example (longestDistance tree-4) = 7
; @example (longestDistance tree-5) = 3
; @example (longestDistance tree-6) = 2
; @example (longestDistance tree-7) = 1
; @example (longestDistance tree-8) = 7
; @example (longestDistance tree-9) = 1
; @example (longestDistance tree-10) = 1
; @example (longestDistance tree-11) = 3
; @example (longestDistance tree-12) = 1
; @example (longestDistance tree-13) = 5
; @example (longestDistance tree-14) = 1
; @example (longestDistance tree-15) = 3
; @example (longestDistance tree-16) = 1
; @example (longestDistance tree-17) = 1
; @example (longestDistance tree-18) = 6
; @example (longestDistance tree-19) = 3
; @example (longestDistance tree-20) = 1
;------------------------------------------------------------------------------
(define (longestDistance T)
(cond
[(empty? T) 0]
[else (max2 (+ 1
(height (BT-left T))
(height (BT-right T)))
(max2 (longestDistance (BT-left T))
(longestDistance (BT-right T)))) ] ) )