Tree traversal: Difference between revisions
Content added Content deleted
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}}==
|