Tree traversal: Difference between revisions
Content added Content deleted
m (→{{header|Quackery}}: tidied up) |
|||
Line 9,607: | Line 9,607: | ||
levelorder: 1 2 3 4 5 6 7 8 9 |
levelorder: 1 2 3 4 5 6 7 8 9 |
||
</pre> |
</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}}== |
=={{header|SequenceL}}== |