Scheme로 구현한 가장 기본적인 이진트리

교수님께서 장장 일주일 전에 내주신 레포트를 내기 하루전에 시작했다.

흠 Scheme 문법이 생소하기도 하고, 내 생각이 폭넓지 못해 두어시간 고생한듯 싶다.

Source Code

#lang scheme
(define (!= arg1 arg2) (not (eq? arg1 arg2))) ; primitive type와 nil type를 비교하기 위한
(define nil '())
(define make-node  (lambda (value left right) (cons value (cons left right))))
(define node-value (lambda (node) (car node)))
(define left-node  (lambda (node) (car (cdr node))))
(define right-node (lambda (node) (cdr (cdr node))))
(define print-tree (lambda (tree) (times-print-tree tree 0)))
(define print-blank (lambda (n) (when (> n 0) (display " ") (print-blank (- n 1)))))

(define times-print-tree
  (lambda (node times)
    (print-blank times)
    (display (node-value node))
    (display "\n")
    (if (!= (left-node node) nil) (times-print-tree (left-node node) (+ times 4)) (display ""))
    (if (!= (right-node node) nil) (times-print-tree (right-node node) (+ times 4)) (display""))
    )
  )

(define tree1 (make-node 1 (make-node 2 (make-node 4 nil nil) (make-node 5 nil nil)) (make-node 3 (make-node 6 nil nil) nil)))

(define node6 (make-node 6 nil nil))
(define node5 (make-node 5 nil nil))
(define node4 (make-node 4 nil nil))
(define node3 (make-node 3 node6 nil))
(define node2 (make-node 2 node4 node5))
(define node1 (make-node 1 node2 node3))

(define tree2 node1)
(print-tree tree1)
(display "---------------------------------------------------\n")
(print-tree tree2)

Output

1
    2
        4
        5
    3
        6
---------------------------------------------------
1
    2
        4
        5
    3
        6