fork download
copy 
  1. #lang racket
  2.  
  3. ;; Define a binary tree structure
  4. (define-struct node (data left right))
  5.  
  6. ;; A Binary Tree of X (BTOFX) is:
  7. ;; - #false (empty tree)
  8. ;; - (make-node X BTOFX BTOFX)
  9.  
  10. (define LEAF #false)  ;; Represents an empty tree
  11.  
  12. ;; =====================================
  13. ;; Problem 1 - bt/map
  14. ;; =====================================
  15. ;; bt/map : (X -> Y) BTOFX -> BTOFY
  16. ;; Applies a function f to every node's data in the tree
  17. ;; Produces a new tree with transformed values
  18.  
  19. (define (bt/map f tree)
  20.   (if (false? tree) 
  21.       LEAF  ;; If the tree is empty, return an empty tree
  22.       (make-node (f (node-data tree))   ;; Apply f to current node data
  23.                  (bt/map f (node-left tree))  ;; Recursive call on left subtree
  24.                  (bt/map f (node-right tree)))))  ;; Recursive call on right subtree
  25.  
  26. ;; =====================================
  27. ;; Problem 2 - bt/fold
  28. ;; =====================================
  29. ;; bt/fold : (X Y Y -> Y) Y BTOFX -> Y
  30. ;; Reduces a tree using a combining function and a base case
  31.  
  32. (define (bt/fold combine base tree)
  33.   (if (false? tree)
  34.       base  ;; If tree is empty, return base case value
  35.       (combine (node-data tree)  
  36.                (bt/fold combine base (node-left tree))  
  37.                (bt/fold combine base (node-right tree)))))
  38.  
  39. ;; =====================================
  40. ;; Example Binary Tree
  41. ;; =====================================
  42. ;; Constructing the following tree:
  43. ;;         1
  44. ;;       /   \
  45. ;;      2     3
  46. ;;     / \   / \
  47. ;;    4   5 6   7
  48. (define tree 
  49.   (make-node 1 
  50.              (make-node 2 
  51.                         (make-node 4 LEAF LEAF) 
  52.                         (make-node 5 LEAF LEAF))
  53.              (make-node 3 
  54.                         (make-node 6 LEAF LEAF) 
  55.                         (make-node 7 LEAF LEAF))))
  56.  
  57. ;; =====================================
  58. ;; Testing bt/map
  59. ;; =====================================
  60. ;; Example: Increment each value in the tree
  61. (define (increment x) (+ x 1))
  62. (define new-tree (bt/map increment tree))
  63.  
  64. ;; Expected structure:
  65. ;;         2
  66. ;;       /   \
  67. ;;      3     4
  68. ;;     / \   / \
  69. ;;    5   6 7   8
  70.  
  71. (displayln "Tree with incremented values:")
  72. (display new-tree)
  73. (newline)
  74.  
  75. ;; Example: Doubling each value
  76. (define double-tree (bt/map (lambda (x) (* x 2)) tree))
  77.  
  78. (displayln "Tree with doubled values:")
  79. (display double-tree)
  80. (newline)
  81.  
  82. ;; =====================================
  83. ;; Testing bt/fold
  84. ;; =====================================
  85. ;; Example: Compute sum of all elements
  86. (define tree-sum (bt/fold (lambda (data left right) (+ data left right)) 0 tree))
  87. (displayln "Sum of all elements:")
  88. (display tree-sum)  ;; Expected output: 1+2+3+4+5+6+7 = 28
  89. (newline)
  90.  
  91. ;; Example: Compute maximum value
  92. (define tree-max (bt/fold (lambda (data left right) (max data left right)) -inf.0 tree))
  93. (displayln "Maximum value in tree:")
  94. (display tree-max)  ;; Expected output: 7
  95. (newline)
  96.  
  97. ;; Example: Count nodes
  98. (define node-count (bt/fold (lambda (_ left right) (+ 1 left right)) 0 tree))
  99. (displayln "Number of nodes in tree:")
  100. (display node-count)  ;; Expected output: 7
  101. (newline)
  102.  
  103. ;; Example: Convert tree to a list (in-order traversal)
  104. (define tree-to-list (bt/fold (lambda (data left right) (append left (list data) right)) '() tree))
  105. (displayln "Tree elements in-order:")
  106. (display tree-to-list)  ;; Expected output: (4 2 5 1 6 3 7)
  107. (newline)
  108.  
Success #stdin #stdout 0.68s 99472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9OYtEq
language:
Racket (racket 7.0)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!