sci:cs:scheme:tree [BaseVolving]

- Tree Algorhtims in Scheme
  - Difination
  - Operations on Binary Trees

Tree Algorhtims in Scheme

Tree is an abstract data structure. In scheme, it is mainly inplemented by using struct.

Binary Tree is mainly discussed here.

Difination

Using define-struct to define a Binary Tree.

;;Definition of tree structure:
;;A tree-node structure is
;;1, false, which means there is nothing in the tree, or
;;2, (make-node (s n lc rc), where s is number, n is symbol
;;   and lc, rc tree-node. 
(define-struct node (ssn name left right))

Operations on Binary Trees

Contains?

To determine whether a node is contained by a b-tree. code reveal hidden content

;;contains-bt : number tree-node -> boolean
;;to determine whether tree contains a node structure
;;with soc in the ssn field
;;example : (contains-bt 1 (make-node 0 'a (make-node 1 'b false false)
;;                                          false))
;;          => true
;;          (contains-bt 2 (make-node 0 'a (make-node 1 'b false false)
;;                                          false))
;;          => false
(define (contains-bt soc tree)
  (cond
    [(boolean? tree) false]
    [else
     (or (= (node-ssn tree) soc)
         (or
          (contains-bt soc (node-left tree))
          (contains-bt soc (node-right tree))))]))