Copyright ©
2005 Suradet Jitprapaikulsarn
สงวนลิขสิทธิ์ 2548 สุรเดช จิตประไพกุลศาล
Homework 13 (Due 19 September 2005)
- Write a function, isHeap, to determine whether a binary tree is a
heap tree. A heap tree is a binary tree with the following
properties: For each node in a heap tree, all values in the subtrees are less than the value in the node.
Scheme Solution.
;------------------------------------------------------------------------------
; @description determine whether a binary tree is a heap tree
; @note a heap tree is a binary tree such that for every node, the values in the
; subtrees are less than the value in the current node.
; @remark In order that every value on the subtrees is less than the value
; of the current node, the maximum value of the left branch and the
; maximum value of the right branch must be less than the value of the
; current node.
; @param T a binary tree
; @return true if a binary tree is a binary search tree
; @contract isHeap: BT -> boolean
; @example (isHeap empty) = true
; @example (isHeap tree-1) = true
; @example (isHeap tree-2) = true
; @example (isHeap tree-3) = true
; @example (isHeap tree-4) = true
; @example (isHeap tree-5) = true
; @example (isHeap tree-6) = true
; @example (isHeap tree-7) = true
; @example (isHeap tree-8) = true
; @example (isHeap tree-9) = true
; @example (isHeap tree-10) = true
; @example (isHeap tree-11) = false
; @example (isHeap tree-12) = true
; @example (isHeap tree-13) = false
; @example (isHeap tree-14) = true
; @example (isHeap tree-15) = false
; @example (isHeap tree-16) = true
; @example (isHeap tree-17) = true
; @example (isHeap tree-18) = false
; @example (isHeap tree-19) = false
; @example (isHeap tree-20) = true
;------------------------------------------------------------------------------
(define (isHeap T)
(cond
[(empty? T) true]
[(and (empty? (BT-left T)) (empty? (BT-right T))) true]
[(empty? (BT-left T)) (and (> (BT-data T) (maxValue (BT-right T)))
(isHeap (BT-right T)))]
[(empty? (BT-right T)) (and (> (BT-data T) (maxValue (BT-left T)))
(isHeap (BT-left T)))]
[else (and (> (BT-data T) (maxValue (BT-right T)))
(> (BT-data T) (maxValue (BT-left T)))
(isHeap (BT-right T))
(isHeap (BT-left T)) ) ] ) )
C Solution.
//------------------------------------------------------------------------------
// @description determine whether the value of the current node is less than the
// value of v
// @param T a binary tree
// @param v a value to be compared to
// @return true if T is empty or T->data < v, false otherwise
// @contract isHeap: BT number -> boolean
// @example isHeapHelper(empty, 9) = true
// @example isHeapHelper(&tree_1, 9) = true
// @example isHeapHelper(&tree_2, 9) = true
// @example isHeapHelper(&tree_3, 9) = true
// @example isHeapHelper(&tree_4, 9) = true
// @example isHeapHelper(&tree_5, 9) = true
// @example isHeapHelper(&tree_6, 9) = true
// @example isHeapHelper(&tree_7, 9) = true
// @example isHeapHelper(&tree_8, 9) = true
// @example isHeapHelper(&tree_9, 9) = false
// @example isHeapHelper(&tree_10, 9) = false
// @example isHeapHelper(&tree_11, 9) = false
// @example isHeapHelper(&tree_12, 9) = false
// @example isHeapHelper(&tree_13, 9) = false
// @example isHeapHelper(&tree_14, 9) = false
// @example isHeapHelper(&tree_15, 9) = false
// @example isHeapHelper(&tree_16, 9) = false
// @example isHeapHelper(&tree_17, 9) = false
// @example isHeapHelper(&tree_18, 9) = false
// @example isHeapHelper(&tree_19, 9) = false
// @example isHeapHelper(&tree_20, 9) = false
//------------------------------------------------------------------------------
bool isHeapHelper(BTree * T, int v)
{
if (T == 0)
{
return true;
}
else
{
return (T->data < v);
}
}
//------------------------------------------------------------------------------
// @description determine whether a binary tree is a heap tree
// @note a heap tree is a binary tree such that for every node, the values in the
// subtrees are less than the value in the current node.
// @param T a binary tree
// @return true if a binary tree is a binary search tree
// @contract isHeap: BT -> boolean
// @example isHeap(empty) = true
// @example isHeap(&tree_1) = true
// @example isHeap(&tree_2) = true
// @example isHeap(&tree_3) = true
// @example isHeap(&tree_4) = true
// @example isHeap(&tree_5) = true
// @example isHeap(&tree_6) = true
// @example isHeap(&tree_7) = true
// @example isHeap(&tree_8) = true
// @example isHeap(&tree_9) = true
// @example isHeap(&tree_10) = true
// @example isHeap(&tree_11) = false
// @example isHeap(&tree_12) = true
// @example isHeap(&tree_13) = false
// @example isHeap(&tree_14) = true
// @example isHeap(&tree_15) = false
// @example isHeap(&tree_16) = true
// @example isHeap(&tree_17) = true
// @example isHeap(&tree_18) = false
// @example isHeap(&tree_19) = false
// @example isHeap(&tree_20) = true
//------------------------------------------------------------------------------
bool isHeap(BTree * T)
{
if (T == 0)
{
return true;
}
else
{
return isHeapHelper(T->left, T->data) &&
isHeapHelper(T->right, T->data) &&
isHeap(T->left) &&
isHeap(T->right);
}
}
- (Bonus) Write a function, largestGap, to determine the largest difference between two adjacent nodes in a binary tree.
Scheme Solution.
;------------------------------------------------------------------------------
; @description determine the largest gap between two adjacent nodes in a binary
; tree
; @param T a binary tree
; @param parent the value of the parent node
; @param acc the largest gap so far
; @return the largest gap between two adjacent nodes
; @contract largestGapA: BT number number -> number
; @example (largestGapA empty 3 2) = 2
; @example (largestGapA tree-1 2 0) = 1
; @example (largestGapA tree-2 3 0) = 1
; @example (largestGapA tree-3 7 0) = 4
; @example (largestGapA tree-4 5 0) = 1
; @example (largestGapA tree-5 6 0) = 1
; @example (largestGapA tree-6 7 0) = 1
; @example (largestGapA tree-7 9 0) = 4
; @example (largestGapA tree-8 9 0) = 1
; @example (largestGapA tree-9 9 0) = 4
;------------------------------------------------------------------------------
(define (largestGapA T parent acc)
(cond
[(empty? T) acc]
[else (max2 (largestGapA (BT-left T)
(BT-data T)
(max2 (abs (- (BT-data T) parent))
acc))
(largestGapA (BT-right T)
(BT-data T)
(max2 (abs (- (BT-data T) parent))
acc)))]))
;------------------------------------------------------------------------------
; @description determine the largest gap between two adjacent nodes in a binary
; tree
; @param T a binary tree
; @return the largest gap between two adjacent nodes
; @contract largestGap: BT -> number
; @example (largestGap empty) = 0
; @example (largestGap tree-1) = 0
; @example (largestGap tree-2) = 1
; @example (largestGap tree-3) = 1
; @example (largestGap tree-4) = 0
; @example (largestGap tree-5) = 1
; @example (largestGap tree-6) = 1
; @example (largestGap tree-7) = 4
; @example (largestGap tree-8) = 0
; @example (largestGap tree-9) = 4
; @example (largestGap tree-10) = 0
; @example (largestGap tree-11) = 3
; @example (largestGap tree-12) = 0
; @example (largestGap tree-13) = 3
; @example (largestGap tree-14) = 0
; @example (largestGap tree-15) = 3
; @example (largestGap tree-16) = 0
; @example (largestGap tree-17) = 0
; @example (largestGap tree-18) = 5
; @example (largestGap tree-19) = 2
; @example (largestGap tree-20) = 0
;------------------------------------------------------------------------------
(define (largestGap T)
(cond
[(empty? T) 0]
[else (max2 (largestGapA (BT-left T) (BT-data T) 0)
(largestGapA (BT-right T) (BT-data T) 0))]))
C Solution.
//------------------------------------------------------------------------------
// @description determine the largest gap between two adjacent nodes in a binary
// tree
// @param T a binary tree
// @return 0 if T is empty or has only one node, otherwise the largest gap
// between two adjacent nodes
// @contract largestGap: BT -> number
// @example largestGap(empty) = 0
// @example largestGap(tree_1) = 0
// @example largestGap(tree_2) = 1
// @example largestGap(tree_3) = 1
// @example largestGap(tree_4) = 0
// @example largestGap(tree_5) = 1
// @example largestGap(tree_6) = 1
// @example largestGap(tree_7) = 4
// @example largestGap(tree_8) = 0
// @example largestGap(tree_9) = 4
//------------------------------------------------------------------------------
int largestGap(BTree * T)
{
if (T == 0)
{
return 0;
}
else if (T->left == 0 && T->right == 0)
{
return 0;
}
else if (T->left == 0) // but T->right != 0
{
return max2( abs(T->data - T->right->data),
largestGap(T->right) );
}
else if (T->right == 0)
{
return max2( abs(T->data - T->left->data),
largestGap(T->left) );
}
else
{
return max2( max2( abs(T->data - T->left->data),
abs(T->data - T->right->data) ),
max2( largestGap(T->left),
largestGap(T->right) ) );
}
}