Anonymous user
Same fringe: Difference between revisions
→version 1.1: +Scheme version
(→{{header|Clojure}}: slight tweak) |
(→version 1.1: +Scheme version) |
||
Line 1,765:
A difference is: H ¬= δ
</pre>
=={{header|Scheme}}==
Descend provides a list of the first ''unvisited'' nodes at each level of the tree. Two such lists are used as lifo stack cursors to keep track of the remaining tree nodes. The main routine compares the top item of each list (ie the leftmost remaining node) and breaks returning 'false' if different, or calls Ascend to update the lists, with help from Descend. If the end of each list, and therefore each tree, is reached 'true' is returned.
<lang Scheme>; binary tree helpers from "Structure and Interpretation of Computer Programs" 2.3.3
(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right)
(list entry left right))
; returns a list of leftmost nodes from each level of the tree
(define (descend tree ls)
(if (null? (left-branch tree))
(cons tree ls)
(descend (left-branch tree) (cons tree ls))))
; updates the list to contain leftmost nodes from each remaining level
(define (ascend ls)
(cond
((and (null? (cdr ls)) (null? (right-branch (car ls)))) '())
((null? (right-branch (car ls))) (cdr ls))
(else
(let ((ls (cons (right-branch (car ls))
(cdr ls))))
(if (null? (left-branch (car ls)))
ls
(descend (left-branch (car ls)) ls))))))
; loops thru each list until the end (true) or nodes are unequal (false)
(define (same-fringe? t1 t2)
(let next ((l1 (descend t1 '()))
(l2 (descend t2 '())))
(cond
((and (null? l1) (null? l2)) #t)
((= (entry (car l1)) (entry (car l2)))
(next (ascend l1) (ascend l2)))
(else #f))))</lang>
=={{header|Tcl}}==
| |||