Tree traversal: Difference between revisions
→{{header|SequenceL}}
m (→{{header|Quackery}}: tidied up) |
|||
Line 9,607:
levelorder: 1 2 3 4 5 6 7 8 9
</pre>
=={{header|Scheme}}==
<lang scheme>(define (preorder tree)
(if (null? tree)
'()
(append (list (car tree))
(preorder (cadr tree))
(preorder (caddr tree)))))
(define (inorder tree)
(if (null? tree)
'()
(append (inorder (cadr tree))
(list (car tree))
(inorder (caddr tree)))))
(define (postorder tree)
(if (null? tree)
'()
(append (postorder (cadr tree))
(postorder (caddr tree))
(list (car tree)))))
(define (level-order tree)
(define lst '())
(define (traverse nodes)
(if (pair? nodes)
(let ((next-nodes '()))
(do ((p nodes (cdr p)))
((null? p))
(set! lst (cons (caar p) lst))
(let* ((n '())
(n (if (null? (cadar p))
n
(cons (cadar p) n)))
(n (if (null? (caddar p))
n
(cons (caddar p) n))))
(set! next-nodes (append n next-nodes))))
(traverse (reverse next-nodes)))))
(if (null? tree)
'()
(begin
(traverse (list tree))
(reverse lst))))
(define (demonstration tree)
(define (display-values lst)
(do ((p lst (cdr p)))
((null? p))
(display (car p))
(if (pair? (cdr p))
(display " ")))
(newline))
(display "preorder: ") (display-values (preorder tree))
(display "inorder: ") (display-values (inorder tree))
(display "postorder: ") (display-values (postorder tree))
(display "level-order: ") (display-values (level-order tree)))
(define the-task-tree
'(1 (2 (4 (7 () ())
())
(5 () ()))
(3 (6 (8 () ())
(9 () ()))
())))
(demonstration the-task-tree)</lang>
{{out}}
<pre>preorder: 1 2 4 7 5 3 6 8 9
inorder: 7 4 2 5 1 8 6 9 3
postorder: 7 4 5 2 8 9 6 3 1
level-order: 1 2 3 4 5 6 7 8 9</pre>
=={{header|SequenceL}}==
| |||