Data definitions to represent hierarchies
Binary trees
In a binary tree, each data definition has two references back to itself.
Example: a family tree
(define-struct person [name parent1 parent2])
;; A Person is one of:
;; - #false
;; - (make-person String Person Person)
;; Interpretation: a person's name and biological parents;
;; or #false if not known
(define PERSON-0 #false)
(define PERSON-LILY (make-person "Lily" PERSON-0 PERSON-0))
(define PERSON-JAMES (make-person "James" PERSON-0 PERSON-0))
(define PERSON-MOLLY (make-person "MOLLY" PERSON-0 PERSON-0))
(define PERSON-ARTHUR (make-person "ARTHUR" PERSON-0 PERSON-0))
(define PERSON-HARRY (make-person "Harry" PERSON-LILY PERSON-JAMES))
(define PERSON-GINNY (make-person "Giny" PERSON-MOLLY PERSON-ARTHUR))
(define PERSON0-ALBUS (make-person "Albus" PERSON-HARRY PERSON-GINNY))
(define (person-template p)
(cond
[(boolean? p) ...]
[(person? p)
(... (person-name p) ...
(person-template (person-parent1 p)) ...
(person-template (person-parent2 p)) ...)]))Example: finding the number of people in the tree
;; tree-size : Person -> Nat
;; Returns the number of named people in the tree
(check-expect (tree-size PERSON-0) 0)
(check-expect (tree-size PERSON-LILY) 1)
(check-expect (tree-size PERSON-HARRY) 3)
(check-expect (tree-size PERSON0-ALBUS) 7)
(define (tree-size p)
(cond
[(boolean? p) 0]
[(person? p)
(+ 1
(tree-size (person-parent1 p))
(tree-size (person-parent2 p)))]))Example: finding the maximum tree depth at a person
;; tree-depth : Person -> Nat
;; Return the deepest "path" in the tree
(check-expect (tree-depth PERSON-0) 0)
(check-expect (tree-depth PERSON-LILY) 1)
(check-expect (tree-depth PERSON-JAMES) 1)
(check-expect (tree-depth PERSON-GINNY) 2)
(check-expect (tree-depth PERSON-ALBUS) 3)
(define (tree-depth p)
(cond
[(boolean? p) 0]
[(person? p)
(+ 1
(max
(tree-depth (person-parent1 p))
(tree-depth (person-parent2 p))))]))