Tree traversal: Difference between revisions
Content deleted Content added
m →{{header|REBOL}}: renamed second and third with left and right |
PascalABC.NET |
||
(29 intermediate revisions by 15 users not shown) | |||
Line 34:
{{trans|Python: Class based}}
<
Int data
Node? left
Line 44:
.right = right
F preorder(visitor) ->
visitor(.data)
I .left != N
Line 51:
.right.preorder(visitor)
F inorder(visitor) ->
I .left != N
.left.inorder(visitor)
Line 58:
.right.inorder(visitor)
F postorder(visitor) ->
I .left != N
.left.postorder(visitor)
Line 65:
visitor(.data)
F preorder2(&d, level = 0) ->
d[level].append(.data)
I .left != N
Line 105:
print(‘levelorder: ’, end' ‘’)
tree.levelorder(printwithspace)
print()</
{{out}}
Line 114:
levelorder: 1 2 3 4 5 6 7 8 9
</pre>
=={{header|8080 Assembly}}==
<syntaxhighlight lang="asm8080"> org 100h
jmp demo
;;; Traverse tree at DE according to method at BC.
;;; Call routine at HL with DE=<value> for each value encounterd.
travrs: shld trvcb+1 ; Store routine pointer
xchg ; Tree in HL
push b ; Jump to method BC
ret
;;; Preorder traversal
preo: mov a,h
ora l
rz ; Null node = stop
mov e,m
inx h
mov d,m ; Load value
inx h
push h ; Handle value
call trvcb
pop h ; Left node
mov e,m
inx h
mov d,m
inx h
push h ; Save pointer
xchg
call preo
pop h
mov e,m
inx h ; Right node
mov d,m
xchg
jmp preo
;;; Inorder traversal
ino: mov a,h
ora l
rz ; Null node = stop
mov e,m
inx h
mov d,m ; Load value
inx h
push d ; Save value on stack
mov e,m
inx h
mov d,m
inx h ; Load left node
push h ; Save pointer on stack
xchg
call ino ; Traverse left node
pop h
pop d ; Get value
push h
call trvcb ; Handle value
pop h
mov e,m
inx h
mov d,m
xchg
jmp ino ; Traverse right node
;;; Postorder traversal
posto: mov a,h
ora l
rz ; Null node = stop
mov e,m
inx h
mov d,m ; Load value
inx h
push d ; Keep value on stack
mov e,m
inx h
mov d,m
inx h ; Load left node
push h
xchg
call posto ; Traverse left node
pop h
mov e,m
inx h
mov d,m ; Load right node
xchg
call posto ; Traverse right node
pop d ; Get value from stack
jmp trvcb ; Handle value
;;; Level-order traversal
lvlo: shld queue ; Store current node at beginning of queue
lxi h,queue ; HL = Queue start pointer
lxi b,queue+2 ; BC = Queue end pointer
lvllp: mov a,h ; When start == end, stop
cmp b
jnz lvlt ; Not equal
mov a,l
cmp c
rz ; Equal = stop
lvlt: mov e,m ; Load current node in DE
inx h
mov d,m
inx h
mov a,d ; Null node = ignore
ora e
jz lvllp
push h ; Keep queue start pointer
xchg ; HL = current node
mov e,m ; Load value into DE
inx h
mov d,m
inx h
push h ; Keep pointer to left and right nodes
push b ; And pointer to end of queue
call trvcb ; Handle value
pop b ; Restore pointer to end of queue
pop h ; Restore pointer to left and right nodes
mvi d,4 ; D = copy counter
lvlcp: mov a,m ; Copy left and right nodes to queue
stax b
inx h
inx b
dcr d
jnz lvlcp
pop h ; Restore queue stack pointer
jmp lvllp
trvcb: jmp 0 ; Callback pointer
;;; Run examples
demo: lhld 6 ; Move stack to top of memory
sphl
lxi h,0 ; So we can still RET out of the program
push h
lxi h,orders
order: mov e,m ; Get string
inx h
mov d,m
inx h
mov a,e ; 0 = done
ora d
rz
push h ; Print string
call print
pop h
mov c,m ; Load method in BC
inx h
mov b,m
inx h
push h
lxi d,tree ; Tree in DE
lxi h,cb ; Callback in HL
call travrs ; Traverse the tree
lxi d,nl
call print ; Newline
pop h ; Restore table pointer
jmp order
;;; Print the tree value. They're all <10 for the example, so we
;;; don't need multiple digits.
cb: mvi a,'0'
add e
sta nstr
lxi d,nstr
print: mvi c,9 ; CP/M print string call
jmp 5
nstr: db '* $'
nl: db 13,10,'$'
;;; Example tree
tree: dw 1, node2, node3
node2: dw 2, node4, node5
node3: dw 3, node6, 0
node4: dw 4, node7, 0
node5: dw 5, 0, 0
node6: dw 6, node8, node9
node7: dw 7, 0, 0
node8: dw 8, 0, 0
node9: dw 9, 0 ,0
;;; Table of names and orders
orders: dw spreo,preo
dw sino,ino
dw sposto,posto
dw slvlo,lvlo
dw 0
spreo: db 'Preorder: $'
sino: db 'Inorder: $'
sposto: db 'Postorder: $'
slvlo: db 'Level-order: $'
queue: equ $ ; Put level-order queue on heap</syntaxhighlight>
{{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|8086 Assembly}}==
<syntaxhighlight lang="nasm"> cpu 8086
org 100h
section .text
jmp demo
;;; Traverse tree at SI. Call routine at CX with values in AX.
;;; CX must preserve BX, CX, SI, DI.
;;; Preorder traversal
preo: test si,si
jz pdone ; Zero pointer = done
lodsw ; Load value
call cx ; Handle value
push si ; Keep value
mov si,[si] ; Load left node
call preo ; Traverse left node
pop si
mov si,[si+2] ; Load right node
jmp preo ; Traverse right node
;;; Inorder traversal
ino: test si,si
jz pdone ; Zero pointer = done
push si
mov si,[si+2] ; Load left node
call ino ; Traverse left node
pop si
lodsw ; Load value
call cx ; Handle value
mov si,[si+2] ; Load right node
jmp ino ; Traverse right node
;;; Postorder traversal
posto: test si,si
jz pdone ; Zero pointer = done
push si
mov si,[si+2] ; Load left node
call posto ; Traverse left node
pop si
push si
mov si,[si+4] ; Load right node
call posto
pop si ; Load value
lodsw
jmp cx ; Handle value
pdone: ret
;;; Level-order traversal
lvlo: mov di,queue ; DI = queue end pointer
mov ax,si
mov si,di ; SI = queue start pointer
stosw
.step: cmp di,si ; If end == start, done
je pdone
lodsw ; Get next item
test ax,ax ; Null?
jz .step
mov bx,si ; Keep start pointer in BX
mov si,ax ; Load item
lodsw ; Get value
call cx ; Handle value
lodsw ; Copy nodes to queue
stosw
lodsw
stosw
mov si,bx ; Put start pointer back
jmp .step
;;; Demo code
demo: mov si,orders
.loop: lodsw ; Load next order
test ax,ax
jz .done
mov dx,ax ; Print order name
mov ah,9
int 21h
lodsw ; Load order routine
mov bp,si ; Keep SI
mov si,tree ; Traverse the tree
mov cx,pdgt ; Printing the digits
call ax
mov si,bp
jmp .loop
.done: ret
;;; Callback: print single digit
pdgt: add al,'0'
mov [.str],al
mov ah,9
mov dx,.str
int 21h
ret
.str: db '* $'
section .data
;;; List of orders
orders: dw .preo,preo
dw .ino,ino
dw .posto,posto
dw .lvlo,lvlo
dw 0
.preo: db 'Preorder: $'
.ino: db 13,10,'Inorder: $'
.posto: db 13,10,'Postorder: $'
.lvlo: db 13,10,'Level-order: $'
;;; Exampe tree
tree: dw 1,.n2,.n3
.n2: dw 2,.n4,.n5
.n3: dw 3,.n6,0
.n4: dw 4,.n7,0
.n5: dw 5,0,0
.n6: dw 6,.n8,.n9
.n7: dw 7,0,0
.n8: dw 8,0,0
.n9: dw 9,0,0
section .bss
queue: resw 256</syntaxhighlight>
{{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|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program deftree64.s */
Line 505 ⟶ 817:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
=={{header|ACL2}}==
<
(if (endp tree)
nil
Line 554 ⟶ 866:
(defun flatten-level (tree)
(let ((levels (flatten-level-r1 tree 0 nil)))
(flatten-level-r2 levels (len levels))))</
=={{header|Action!}}==
Line 560 ⟶ 872:
The user must type in the monitor the following command after compilation and before running the program!<pre>SET EndProg=*</pre>
{{libheader|Action! Tool Kit}}
<
INCLUDE "D2:ALLOCATE.ACT" ;from the Action! Tool Kit. You must type 'SET EndProg=*' from the monitor after compiling, but before running this program!
Line 810 ⟶ 1,122:
DestroyTree(t)
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Tree_traversal.png Screenshot from Atari 8-bit computer]
Line 821 ⟶ 1,133:
=={{header|Ada}}==
<
with Ada.Unchecked_Deallocation;
with Ada.Containers.Doubly_Linked_Lists;
Line 928 ⟶ 1,240:
New_Line;
Destroy_Tree(N);
end Tree_traversal;</
=={{header|Agda}}==
<
open import Data.Nat using (
open import Level using (Level)
open import Relation.Binary.PropositionalEquality using (
data Tree {a} (A : Set a) : Set a where
leaf : Tree A
node : A
variable
Line 944 ⟶ 1,256:
A : Set a
preorder : Tree A
preorder tr = go tr []
where
go : Tree A
go leaf ys = ys
go (node x ls rs) ys = x
inorder : Tree A
inorder tr = go tr []
where
go : Tree A
go leaf ys = ys
go (node x ls rs) ys = go ls (x
postorder : Tree A
postorder tr = go tr []
where
go : Tree A
go leaf ys = ys
go (node x ls rs) ys = go ls (go rs (x
level-order : Tree A
level-order tr = concat (go tr [])
where
go : Tree A
go leaf qs = qs
go (node x ls rs) [] = (x
go (node x ls rs) (q
example-tree : Tree
example-tree =
node 1
Line 995 ⟶ 1,307:
leaf)
_ : preorder example-tree
_ = refl
_ : inorder example-tree
_ = refl
_ : postorder example-tree
_ = refl
_ : level-order example-tree
_ = refl</
=={{header|ALGOL 68}}==
Line 1,017 ⟶ 1,329:
{{works with|ELLA ALGOL 68|Any (with appropriate job cards)}}
<
PROC value repr = (VALUE value)STRING: whole(value, 0);
Line 1,140 ⟶ 1,452:
destroy tree(node)
)</
Output:
<pre>
Line 1,152 ⟶ 1,464:
Written in Dyalog APL with dfns.
<
inorder
postorder? {l r?? ?? ? ? ? ???(?r)???(×?r)?(?l)???(×?l)??}
lvlorder
These accept four arguments (they are operators, a.k.a. higher-order functions):
<pre>acc visit ___order children bintree</pre>
Line 1,174 ⟶ 1,486:
and empty childL or childR mean and absence of the corresponding child node.
<
visit?{?,(×??)???}
Each time the accumulator is initialised as an empty list. Visiting a node means to append its data to the accumulator, and generating children is fetching the two corresponding sublists in the nested array if they're non-empty.<br>
My input into the interactive APL session is indented by 6 spaces.
<pre>
1 2 4 7 5 3 6 8 9
7 4 2 5 1 8 6 9 3
7 4 5 2 8 9 6 3 1
1 2 3 4 5 6 7 8 9
</pre>
Line 1,198 ⟶ 1,510:
=={{header|AppleScript}}==
{{Trans|JavaScript}}(ES6)
<
-- Sample tree of integers
set tree to node(1, ¬
Line 1,212 ⟶ 1,524:
-- 'Visualize a Tree':
set strTree to unlines({¬
"
"
"
" 1
"
"
"
script tabulate
on |
justifyRight(14, space, s & ": ") & unwords(xs)
end |
end script
Line 1,249 ⟶ 1,561:
-- inorder :: a -> [[a]] -> [a]
on inorder(x, xs)
if {}
item 1 of xs & x & concat(rest of xs)
else
Line 1,272 ⟶ 1,584:
on foldTree(f)
script
on |
script go
property g : |
on |
g(root of oNode, |
of map(go))
end |
end script
|
end |
end script
end foldTree
Line 1,306 ⟶ 1,618:
tell mReturn(contents of f)
repeat with x in xs
set end of lst to |
end repeat
end tell
Line 1,336 ⟶ 1,648:
set lng to length of xs
repeat with i from lng to 1 by -1
set v to |
end repeat
return v
Line 1,369 ⟶ 1,681:
-- values of each level of the tree.
script go
on |
if {}
tell a to set {h, t} to {item 1, rest}
else
Line 1,377 ⟶ 1,689:
{{root of node} & h} & foldr(go, t, nest of node)
end |
end script
|
end levels
Line 1,390 ⟶ 1,702:
else
script
property |
end script
end if
Line 1,401 ⟶ 1,713:
-- to each element of xs.
script
on |
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |
end repeat
return lst
end tell
end |
end script
end map
Line 1,473 ⟶ 1,785:
set ys to {}
repeat with i from 1 to n
set v to |
if missing value is v then
return ys
Line 1,518 ⟶ 1,830:
tell mReturn(f)
repeat with i from 1 to lng
set end of lst to |
end repeat
return lst
end tell
end zipWith</
{{Out}}
<pre>
1
preorder: 1 2 4 7 5 3 6 8 9
inorder: 7 4 2 5 1 8 6 9 3
Line 1,538 ⟶ 1,850:
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
Line 1,975 ⟶ 2,287:
iMagicNumber: .int 0xCCCCCCCD
</syntaxhighlight>
{{output}}
<pre>
Line 2,022 ⟶ 2,334:
=={{header|ATS}}==
<
"share/atspre_staload.hats"
//
Line 2,119 ⟶ 2,431:
println! ("postorder:\t", postorder(t0));
println! ("level-order:\t", levelorder(t0));
end (* end of [main0] *)</
{{out}}
Line 2,129 ⟶ 2,441:
=={{header|AutoHotkey}}==
{{works with|AutoHotkey_L|45}}
<
AddNode(Tree,2,4,5,2)
AddNode(Tree,3,6,0,3)
Line 2,181 ⟶ 2,493:
t .= i%Lev%, Lev++
Return t
}</
=={{header|AWK}}==
<
function preorder(tree, node, res, child) {
if (node == "")
Line 2,274 ⟶ 2,586:
delete result
}
</syntaxhighlight>
=={{header|Bracmat}}==
<
( tree
= 1
Line 2,317 ⟶ 2,629:
& out$("level-order:" levelorder$(!tree.))
&
)</
=={{header|BCPL}}==
<syntaxhighlight lang="bcpl">get "libhdr"
manifest $(
VAL=0
LEFT=1
RIGHT=2
$)
let tree(v,l,r) = valof
$( let obj = getvec(2)
obj!VAL := v
obj!LEFT := l
obj!RIGHT := r
resultis obj
$)
let preorder(tree, cb) be unless tree=0
$( cb(tree!VAL)
preorder(tree!LEFT, cb)
preorder(tree!RIGHT, cb)
$)
let inorder(tree, cb) be unless tree=0
$( inorder(tree!LEFT, cb)
cb(tree!VAL)
inorder(tree!RIGHT, cb)
$)
let postorder(tree, cb) be unless tree=0
$( postorder(tree!LEFT, cb)
postorder(tree!RIGHT, cb)
cb(tree!VAL)
$)
let levelorder(tree, cb) be
$( let q=vec 255
let s=0 and e=1
q!0 := tree
until s=e do
$( unless q!s=0 do
$( q!e := q!s!LEFT
q!(e+1) := q!s!RIGHT
e := e+2
cb(q!s!VAL)
$)
s := s+1
$)
$)
let traverse(name, order, tree) be
$( let cb(n) be writef("%N ", n)
writef("%S:*T", name)
order(tree, cb)
wrch('*N')
$)
let start() be
$( let example = tree(1, tree(2, tree(4, tree(7, 0, 0), 0),
tree(5, 0, 0)),
tree(3, tree(6, tree(8, 0, 0),
tree(9, 0, 0)),
0))
traverse("preorder", preorder, example)
traverse("inorder", inorder, example)
traverse("postorder", postorder, example)
traverse("level-order", levelorder, example)
$)</syntaxhighlight>
{{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|C}}==
<
#include <stdio.h>
Line 2,465 ⟶ 2,850:
return 0;
}</
=={{header|C sharp}}==
<
using System.Collections.Generic;
using System.Linq;
Line 2,539 ⟶ 2,924:
Console.WriteLine("{0}:\t{1}", traversal.Method.Name, string.Join(" ", traversal()));
}
}</
=={{header|C++}}==
Line 2,546 ⟶ 2,931:
{{libheader|Boost|1.39.0}}
<
#include <iostream>
#include <queue>
Line 2,639 ⟶ 3,024:
return 0;
}</
===Array version===
<
using namespace std;
Line 2,710 ⟶ 3,095:
level_order(t);
cout << endl;
}</
===Modern C++===
{{works with|C++14}}
<
#include <memory>
#include <queue>
Line 2,808 ⟶ 3,193:
n.level_order(print);
std::cout << '\n';
}</
{{out}}
Line 2,819 ⟶ 3,204:
=={{header|Ceylon}}==
<
ArrayList
}
Line 2,915 ⟶ 3,300:
levelOrder(tree);
print("");
}</
=={{header|Clojure}}==
<
(when node
(doseq [o order]
Line 2,961 ⟶ 3,346:
(print (format "%-12s" (str f ":")))
((resolve f) tree pr-node)
(println)))</
=={{header|CLU}}==
<
pre_order, post_order, in_order, level_order
branch = struct[left, right: bintree[T], val: T]
Line 3,057 ⟶ 3,442:
stream$puts(po, " " || int$unparse(i))
end
end start_up</
{{out}}
<pre>preorder: 1 2 4 7 5 3 6 8 9
Line 3,065 ⟶ 3,450:
=={{header|CoffeeScript}}==
<
# In this example, we don't encapsulate binary trees as objects; instead, we have a
# convention on how to store them as arrays, and we namespace the functions that
Line 3,112 ⟶ 3,497:
test_walk "postorder"
test_walk "levelorder"
</syntaxhighlight>
output
<
> coffee tree_traversal.coffee
preorder 1 2 4 7 5 3 6 8 9
Line 3,120 ⟶ 3,505:
postorder 7 4 5 2 8 9 6 3 1
levelorder 1 2 3 4 5 6 7 8 9
</
=={{header|Common Lisp}}==
<
(when node
(funcall f (first node))
Line 3,161 ⟶ 3,546:
(funcall traversal-function *tree* (lambda (value) (format t " ~A" value))))
(map nil #'show '(preorder inorder postorder level-order))</
Output:
Line 3,172 ⟶ 3,557:
=={{header|Coq}}==
<
Require Import List.
Line 3,181 ⟶ 3,566:
Fixpoint height (t: tree) : nat :=
1 + fold_left (
Example leaf n : tree := {| value := n ; children := nil |}.
Line 3,199 ⟶ 3,584:
match c with
| nil => n :: nil
|
end.
Line 3,212 ⟶ 3,597:
| O => nil
| S fuel' =>
let '(p, f) := fold_right (
p ++ levelorder_forest fuel' f
end.
Line 3,223 ⟶ 3,608:
Compute postorder t9.
Compute levelorder t9.
</syntaxhighlight>
=={{header|Crystal}}==
{{trans|C++}}
<
class Node(T)
property left : Nil | Node(T)
Line 3,309 ⟶ 3,694:
puts
</syntaxhighlight>
Output:
<pre>
Line 3,320 ⟶ 3,705:
=={{header|D}}==
This code is long because it's very generic.
<
const final class Node(T) {
Line 3,396 ⟶ 3,781:
tree.levelOrder;
writeln;
}</
{{out}}
<pre> preOrder: 1 2 4 7 5 3 6 8 9
Line 3,406 ⟶ 3,791:
{{trans|Haskell}}
Generic as the first version, but not lazy as the Haskell version.
<
T v;
Node* l, r;
Line 3,449 ⟶ 3,834:
writeln(postOrder(tree));
writeln(levelOrder(tree));
}</
{{out}}
<pre>[1, 2, 4, 7, 5, 3, 6, 8, 9]
Line 3,458 ⟶ 3,843:
===Alternative Lazy Version===
This version is not complete, it lacks the level order visit.
<
const struct Tree(T) {
Line 3,522 ⟶ 3,907:
tree.inOrder.map!(t => t.value).writeln;
tree.postOrder.map!(t => t.value).writeln;
}</
{{out}}
<pre>[1, 2, 4, 7, 5, 3, 6, 8, 9]
[7, 4, 2, 5, 1, 8, 6, 9, 3]
[7, 4, 5, 2, 8, 9, 6, 3, 1]</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
{Structure holding node data}
type PNode = ^TNode;
TNode = record
Data: integer;
Left,Right: PNode;
end;
function PreOrder(Node: TNode): string;
{Recursively traverse Node-Left-Right}
begin
Result:=IntToStr(Node.Data);
if Node.Left<>nil then Result:=Result+' '+PreOrder(Node.Left^);
if Node.Right<>nil then Result:=Result+' '+PreOrder(Node.Right^);
end;
function InOrder(Node: TNode): string;
{Recursively traverse Left-Node-Right}
begin
Result:='';
if Node.Left<>nil then Result:=Result+inOrder(Node.Left^);
Result:=Result+IntToStr(Node.Data)+' ';
if Node.Right<>nil then Result:=Result+inOrder(Node.Right^);
end;
function PostOrder(Node: TNode): string;
{Recursively traverse Left-Right-Node}
begin
Result:='';
if Node.Left<>nil then Result:=Result+PostOrder(Node.Left^);
if Node.Right<>nil then Result:=Result+PostOrder(Node.Right^);
Result:=Result+IntToStr(Node.Data)+' ';
end;
function LevelOrder(Node: TNode): string;
{Traverse the tree at each level, Left to right}
var Queue: TList;
var NT: TNode;
begin
Queue:=TList.Create;
try
Result:='';
Queue.Add(@Node);
while true do
begin
{Display oldest node in queue}
NT:=PNode(Queue[0])^;
Queue.Delete(0);
Result:=Result+IntToStr(NT.Data)+' ';
{Queue left and right children}
if NT.left<>nil then Queue.add(NT.left);
if NT.right<>nil then Queue.add(NT.right);
if Queue.Count<1 then break;
end;
finally Queue.Free; end;
end;
procedure ShowBinaryTree(Memo: TMemo);
var Tree: array [0..9] of TNode;
var I: integer;
begin
{Fill array of node with data}
{that matchs its position in the array}
for I:=0 to High(Tree) do
begin
Tree[I].Data:=I+1;
Tree[I].Left:=nil;
Tree[I].Right:=nil;
end;
{Build the specified tree}
Tree[0].left:=@Tree[2-1];
Tree[0].right:=@Tree[3-1];
Tree[1].left:=@Tree[4-1];
Tree[1].right:=@Tree[5-1];
Tree[3].left:=@Tree[7-1];
Tree[2].left:=@Tree[6-1];
Tree[5].left:=@Tree[8-1];
Tree[5].right:=@Tree[9-1];
{Tranverse the tree in four specified ways}
Memo.Lines.Add('Pre-Order: '+PreOrder(Tree[0]));
Memo.Lines.Add('In-Order: '+InOrder(Tree[0]));
Memo.Lines.Add('Post-Order: '+PostOrder(Tree[0]));
Memo.Lines.Add('Level-Order: '+LevelOrder(Tree[0]));
end;
</syntaxhighlight>
{{out}}
<pre>
Pre-Order: 1 2 4 7 5 3 6 8 9
In-Order: 7 4 2 5 1 8 6 9 3
Post-Order: 7 4 5 2 8 9 6 3 1
Level-Order: 1 2 3 4 5 6 7 8 9
Elapsed Time: 4.897 ms.
</pre>
=={{header|Draco}}==
<syntaxhighlight lang="draco">type
Node = struct {
int val;
*Node left, right;
},
Tree = *Node;
proc tree(int v; Tree l, r) Tree:
Tree t;
t := new(Node);
t*.val := v;
t*.left := l;
t*.right := r;
t
corp
proc preorder(Tree t) void:
if t /= nil then
write(t*.val, ' ');
preorder(t*.left);
preorder(t*.right)
fi
corp
proc inorder(Tree t) void:
if t /= nil then
inorder(t*.left);
write(t*.val, ' ');
inorder(t*.right)
fi
corp
proc postorder(Tree t) void:
if t /= nil then
postorder(t*.left);
postorder(t*.right);
write(t*.val, ' ')
fi
corp
proc levelorder(Tree t) void:
[256]Tree q;
word s, e;
s := 0;
q[s] := t;
e := 1;
while s /= e do
if q[s] /= nil then
q[e] := q[s]*.left;
q[e+1] := q[s]*.right;
e := e+2;
write(q[s]*.val, ' ')
fi;
s := s+1
od
corp
proc main() void:
Tree t;
t := tree(1,
tree(2,
tree(4,
tree(7,nil,nil),
nil),
tree(5,nil,nil)),
tree(3,
tree(6,
tree(8,nil,nil),
tree(9,nil,nil)),
nil));
write("preorder: "); preorder(t); writeln();
write("inorder: "); inorder(t); writeln();
write("postorder: "); postorder(t); writeln();
write("level-order: "); levelorder(t); writeln();
corp</syntaxhighlight>
{{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|E}}==
<
null],
[5, null, null]],
Line 3,576 ⟶ 4,155:
print("level-order:")
levelOrder(btree, fn v { print(" ", v) })
println()</
=={{header|EasyLang}}==
{{trans|C}}
<syntaxhighlight lang=easylang>
tree[] = [ 1 2 3 4 5 6 -1 7 -1 -1 -1 8 9 ]
#
proc preorder ind . .
if ind > len tree[] or tree[ind] = -1
return
.
write " " & tree[ind]
preorder ind * 2
preorder ind * 2 + 1
.
write "preorder:"
preorder 1
print ""
#
proc inorder ind . .
if ind > len tree[] or tree[ind] = -1
return
.
inorder ind * 2
write " " & tree[ind]
inorder ind * 2 + 1
.
write "inorder:"
inorder 1
print ""
#
proc postorder ind . .
if ind > len tree[] or tree[ind] = -1
return
.
postorder ind * 2
postorder ind * 2 + 1
write " " & tree[ind]
.
write "postorder:"
postorder 1
print ""
#
global tail head queue[] .
proc initqu n . .
len queue[] n
tail = 1
head = 1
.
proc enqu v . .
queue[tail] = v
tail = (tail + 1) mod1 len queue[]
.
func dequ .
if head = tail
return -1
.
h = head
head = (head + 1) mod1 len queue[]
return queue[h]
.
initqu len tree[]
proc levelorder n . .
enqu n
repeat
ind = dequ
until ind = -1
if ind < len tree[] and tree[ind] <> -1
write " " & tree[ind]
enqu ind * 2
enqu ind * 2 + 1
.
.
.
write "level-order:"
levelorder 1
print ""
</syntaxhighlight>
{{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
</pre>
=={{header|Eiffel}}==
Line 3,582 ⟶ 4,245:
Void-Safety has been disabled for simplicity of the code.
<
description : "Application for tree traversal demonstration"
output : "[
Line 3,632 ⟶ 4,295:
end
end -- class APPLICATION</
<
description : "A simple node for a binary tree"
libraries : "Relies on LINKED_LIST from EiffelBase"
Line 3,759 ⟶ 4,422:
end
-- class NODE</
=={{header|Elena}}==
ELENA
<
import extensions'routines;
import system'collections;
Line 3,775 ⟶ 4,438:
class Node
{
constructor new(int value)
Line 3,841 ⟶ 4,504:
LevelOrder = new Enumerable
{
Queue<Node> queue := class Queue<Node>.allocate(4).push
Enumerator enumerator() = new Enumerator
Line 3,847 ⟶ 4,510:
bool next() = queue.isNotEmpty();
get Value()
{
Node item := queue.pop();
Line 3,883 ⟶ 4,546:
console.printLine("Postorder :", tree.Postorder);
console.printLine("LevelOrder:", tree.LevelOrder)
}</
{{out}}
<pre>
Line 3,894 ⟶ 4,557:
=={{header|Elisa}}==
This is a generic component for binary tree traversals. More information about binary trees in Elisa are given in [http://jklunder.home.xs4all.nl/elisa/part02/doc030.html trees].
<syntaxhighlight lang="elisa">
component BinaryTreeTraversals (Tree, Element);
type Tree;
Line 3,931 ⟶ 4,594:
];
end component BinaryTreeTraversals;
</syntaxhighlight>
Tests
<syntaxhighlight lang="elisa">
use BinaryTreeTraversals (Tree, integer);
Line 3,953 ⟶ 4,616:
{Item(Level_order(BT))}?
{ 1, 2, 3, 4, 5, 6, 7, 8, 9}
</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Erlang}}
<
defp tnode, do: {}
defp tnode(v), do: {:node, v, {}, {}}
Line 4,012 ⟶ 4,675:
end
Tree_Traversal.main</
{{out}}
Line 4,020 ⟶ 4,683:
postorder: 7 4 5 2 8 9 6 3 1
levelorder: 1 2 3 4 5 6 7 8 9
</pre>
=={{header|EMal}}==
{{trans|Java}}
<syntaxhighlight lang="emal">
type Node
model
:T value
Node left
Node right
new by generic T, :T ←value do end
fun visit ← <|write(me.value + " ")
end
type Order
enum
int PREORDER, INORDER, POSTORDER, LEVELORDER
end
type Main
fun traverse ← void by Node node, Order order
if node æ null do return end
if order æ Order.PREORDER
node.visit()
traverse(node.left, order)
traverse(node.right, order)
else if order æ Order.INORDER
traverse(node.left, order)
node.visit()
traverse(node.right, order)
else if order æ Order.POSTORDER
traverse(node.left, order)
traverse(node.right, order)
node.visit()
else if order æ Order.LEVELORDER
List queue ← Node[]
queue.insertFirst(node)
while not queue.isEmpty()
Node next ← queue.deleteLast()
next.visit()
if next.left ≠ null do queue.insertFirst(next.left) end
if next.right ≠ null do queue.insertFirst(next.right) end
end
end
end
Node one ← Node(int, 1)
Node two ← Node(int, 2)
Node three ← Node(int, 3)
Node four ← Node(int, 4)
Node five ← Node(int, 5)
Node six ← Node(int, 6)
Node seven ← Node(int, 7)
Node eight ← Node(int, 8)
Node nine ← Node(int, 9)
one.left ← two
one.right ← three
two.left ← four
two.right ← five
three.left ← six
four.left ← seven
six.left ← eight
six.right ← nine
traverse(one, Order.PREORDER)
writeLine()
traverse(one, Order.INORDER)
writeLine()
traverse(one, Order.POSTORDER)
writeLine()
traverse(one, Order.LEVELORDER)
writeLine()
</syntaxhighlight>
{{out}}
<pre>
1 2 4 7 5 3 6 8 9
7 4 2 5 1 8 6 9 3
7 4 5 2 8 9 6 3 1
1 2 3 4 5 6 7 8 9
</pre>
=={{header|Erlang}}==
<
-export([main/0]).
-export([preorder/2, inorder/2, postorder/2, levelorder/2]).
Line 4,064 ⟶ 4,802:
inorder(F, Tree), ?NEWLINE,
postorder(F, Tree), ?NEWLINE,
levelorder(F, Tree), ?NEWLINE.</
Output:
Line 4,074 ⟶ 4,812:
=={{header|Euphoria}}==
<
constant tree = {1,
Line 4,140 ⟶ 4,878:
puts(1,"level-order: ")
level_order(tree)
puts(1,'\n')</
Output:
Line 4,149 ⟶ 4,887:
=={{header|F_Sharp|F#}}==
<
open System.IO
Line 4,223 ⟶ 4,961:
printf "\nlevel-order: "
levelorder tree |> Seq.iter show
0</
=={{header|Factor}}==
<
math.parser ;
IN: rosetta.tree-traversal
Line 4,297 ⟶ 5,035:
[ "levelorder: " write levelorder nl ]
[ "levelorder2: " write levelorder2 nl ]
} 2cleave ;</
=={{header|Fantom}}==
<
class Tree
{
Line 4,370 ⟶ 5,108:
}
}
</syntaxhighlight>
Output:
Line 4,381 ⟶ 5,119:
=={{header|Forth}}==
<
: node ( l r data -- node ) here >r , , , r> ;
: leaf ( data -- node ) 0 0 rot node ;
Line 4,436 ⟶ 5,174:
cr ' . tree postorder \ 7 4 5 2 8 9 6 3 1
cr tree max-depth . \ 4
cr ' . tree levelorder \ 1 2 3 4 5 6 7 8 9</
=={{header|Fortran}}==
Line 4,446 ⟶ 5,184:
Otherwise, one can always write detailed code that gives effect to recursive usage, typically involving a variable called SP and an array called STACK. Oddly, such proceedings for the QuickSort algorithm are often declared to be "iterative", presumably because the absence of formally-declared recursive phrases blocks recognition of recursive action.
In the example source, the mainline, GORILLA, does its recursion via array twiddling and in that spirit, uses multiple lists for the "level" style traversal so that one tree clamber only need be made, whereas the recursive equivalent cheats by commanding one clamber for each level. The recursive routines store their state in part via the position within their code - that is, before, between, or after the recursive invocations, and are much easier to compare. Rather than litter the source with separate routines and their declarations for each of the four styles required, routine TARZAN has the four versions together for easy comparison, distinguished by a CASE statement. Actually, the code could be even more compact as in <
IF (STYLE.EQ."PRE") CALL OUT(HAS)
IF (LINKL(HAS).GT.0) CALL TARZAN(LINKL(HAS),STYLE)
IF (STYLE.EQ."IN") CALL OUT(HAS)
IF (LINKR(HAS).GT.0) CALL TARZAN(LINKR(HAS),STYLE)
IF (STYLE.EQ."POST") CALL OUT(HAS)</
But that would cloud the simplicity of each separate version, and would be extra messy with the fourth option included. On the other hand, the requirements for formal recursion carry the cost of the entry/exit protocol and moreover must do so for every invocation (though there is sometimes opportunity for end-recursion to be converted into a secret "go to") - avoiding this is why every invocation of TARZAN first checks that it has a live link, rather than coding this once only within TARZAN to return immediately when invoked with a dead link - whereas the array twiddling via SP deals only with what is required and notably, avoids raising the stack if it can. Further, the GORILLA version can if necessary maintain additional information, as is needed for the postorder traversal where, not having state information stored via position in the code (as with the recursive version) it needs to know whether it is returning to a node from which it departed via the rightwards link and so is in the post-traversal state and thus due a postorder action. This could involve an auxiliary array, but here is handled by taking advantage of the sign of the STACK element. This sort of trick might still be possible even if the link values were memory addresses rather than array indices, as many computers do not use their full word size for addressing.
Line 4,458 ⟶ 5,196:
Except for the usage of array MIST having an element zero and the use of an array assignment MIST(:,0) = 0, the GORILLA code is old-style Fortran. One could play tricks with EQUIVALENCE statements to arrange that an array's first element was at index zero, but that would rely on the absence of array bound checking and is more difficult with multi-dimensional arrays. Instead, one would make do either by having a separate list length variable, or else remembering the offsets... The MODULE usage requires F90 or later and provides a convenient protocol for global data, otherwise one must mess about with COMMON or parameter hordes. If that were done, the B6700 compiler would have handled it. But for the benefit of trembling modern compilers it also contains the fearsome new attribute, RECURSIVE, to flog the compilers into what was formalised for Algol in 1960 and was available ''for free'' via Burroughs in the 1970s.
On the other hand, the early-style Fortran DO-loop would always execute once, because the test was made only at the end of an iteration, and here, routine JANE does not know the value of MAXLEVEL until ''after'' the first iteration. Code such as <
DO GASP = 1,MAXLEVEL
CALL TARZAN(1,HOW)
END DO</
Would not work with modern Fortran, because the usual approach is to calculate the iteration count from the DO-loop parameters at the ''start'' of the DO-loop, and possibly not execute it at all if that count is not positive. This also means that with each iteration, the count must be decremented ''and'' the index variable adjusted; extra effort. There is no equivalent of Pascal's <code>Repeat ... until ''condition'';</code>, so, in place of a nice "structured" statement with clear interpretation, there is some messy code with a label and a GO TO, oh dear.
===Source===
<syntaxhighlight lang="fortran">
MODULE ARAUCARIA !Cunning crosswords, also.
INTEGER ENUFF !To suit the set example.
Line 4,668 ⟶ 5,406:
CALL JANE("LEVEL") !Alternatively...
END !So much for that.
</syntaxhighlight>
===Output===
Alternately GORILLA-style, and JANE-style:
Line 4,687 ⟶ 5,425:
=={{header|FreeBASIC}}==
<
#define NULL 0
Line 4,760 ⟶ 5,498:
Wend
End Sub
</syntaxhighlight>
{{out}}
<pre>
Line 4,772 ⟶ 5,510:
=={{header|FunL}}==
{{trans|Haskell}}
<
def
Line 4,807 ⟶ 5,545:
println( inorder(tree) )
println( postorder(tree) )
println( levelorder(tree) )</
{{out}}
Line 4,820 ⟶ 5,558:
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Tree_traversal}}
'''Solution'''
Notice that the action to do when visiting a node is provided as a lambda expression:
[[File:Fōrmulæ - Tree traversal 01.png]]
[[File:Fōrmulæ - Tree traversal 02.png]]
[[File:Fōrmulæ - Tree traversal 03.png]]
[[File:Fōrmulæ - Tree traversal 04.png]]
'''Test case for pre-order'''
[[File:Fōrmulæ - Tree traversal 05.png]]
[[File:Fōrmulæ - Tree traversal 06.png]]
'''Test case for in-order'''
[[File:Fōrmulæ - Tree traversal 07.png]]
[[File:Fōrmulæ - Tree traversal 08.png]]
'''Test case for post-order'''
[[File:Fōrmulæ - Tree traversal 09.png]]
[[File:Fōrmulæ - Tree traversal 10.png]]
'''Test case for breadth-first search'''
[[File:Fōrmulæ - Tree traversal 11.png]]
[[File:Fōrmulæ - Tree traversal 12.png]]
=={{header|GFA Basic}}==
<syntaxhighlight lang="basic">
maxnodes%=100 ! set a limit to size of tree
content%=0 ! index of content field
Line 4,945 ⟶ 5,715:
WEND
RETURN
</syntaxhighlight>
=={{header|Go}}==
Line 4,951 ⟶ 5,721:
{{trans|C}}
This is like many examples on this page.
<
import "fmt"
Line 5,036 ⟶ 5,806:
func visitor(value int) {
fmt.Print(value, " ")
}</
{{out}}
<pre>
Line 5,046 ⟶ 5,816:
===Flat slice===
Alternative representation. Like Wikipedia [http://en.wikipedia.org/wiki/Binary_tree#Arrays Binary tree#Arrays]
<
import "fmt"
Line 5,116 ⟶ 5,886:
}
}
}</
=={{header|Groovy}}==
Uses Groovy '''Node''' and '''NodeBuilder''' classes
<
preorder = { Node node ->
([node] + node.children().collect { preorder(it) }).flatten()
Line 5,154 ⟶ 5,924:
node
}
}</
Verify that '''BinaryNodeBuilder''' will not allow a node to have more than 2 children
<
new BinaryNodeBuilder().'1' {
a {}
Line 5,166 ⟶ 5,936:
} catch (org.codehaus.groovy.transform.powerassert.PowerAssertionError e) {
println 'limited to binary tree\r\n'
}</
Test case #1 (from the task definition)
<
// / \
// 2 3
Line 5,185 ⟶ 5,955:
'6' { '8' {}; '9' {} }
}
}</
Test case #2 (tests single right child)
<
// / \
// 2 3
Line 5,204 ⟶ 5,974:
'6' { '8' {}; '9' {} }
}
}</
Run tests:
<
println "preorder: ${preorder(tree).collect{it.name()}}"
println "preorder: ${tree.depthFirst().collect{it.name()}}"
Line 5,221 ⟶ 5,991:
}
test(tree1)
test(tree2)</
Output:
Line 5,242 ⟶ 6,012:
=={{header|Haskell}}==
===Left Right nodes===
<
data Tree a
Line 5,311 ⟶ 6,081:
([preorder, inorder, postorder, levelorder] <*> [tree])
where
justifyLeft n c s = take n (s <> replicate n c)</
{{Out}}
<pre> 1
Line 5,332 ⟶ 6,102:
{{Trans|Python}}
<syntaxhighlight lang
import Data.Tree (Tree (..), drawForest, drawTree, foldTree)
---------------------- TREE TRAVERSAL --------------------
Line 5,365 ⟶ 6,136:
Int -> [Int] -> Int
nodeCount = const (succ . sum)
treeDepth = const (succ . foldr max 1)
treeMax x xs = maximum (x : xs)
treeMin x xs = minimum (x : xs)
treeProduct x xs = x * product xs
treeSum x xs = x + sum xs
treeWidth _ [] = 1
treeWidth _ xs = sum xs
treeLeaves :: Tree a -> [a]
treeLeaves = foldTree go
where
go
go
--------------------------- TEST -------------------------
tree :: Tree Int
Line 5,424 ⟶ 6,189:
justifyLeft, justifyRight :: Int -> Char -> String -> String
justifyLeft n c s = take n (s <> replicate n c)
justifyRight n c = (drop . length) <*> (replicate n c <>)</
<pre>1
|
Line 5,457 ⟶ 6,222:
=={{header|Icon}} and {{header|Unicon}}==
<
bTree := [1, [2, [4, [7]], [5]], [3, [6, [8], [9]]]]
showTree(bTree, preorder|inorder|postorder|levelorder)
Line 5,488 ⟶ 6,253:
}
}
end</
Output:
Line 5,500 ⟶ 6,265:
=={{header|Isabelle}}==
<
imports Main
begin
Line 5,507 ⟶ 6,272:
definition example :: "int tree" where
"example
Node
(Node
Line 5,529 ⟶ 6,294:
)"
fun preorder :: "'a tree
"preorder Leaf = []"
| "preorder (Node l a r) = a # preorder l @ preorder r"
Line 5,535 ⟶ 6,300:
lemma "preorder example = [1, 2, 4, 7, 5, 3, 6, 8, 9]" by code_simp
fun inorder :: "'a tree
"inorder Leaf = []"
| "inorder (Node l a r) = inorder l @ [a] @ inorder r"
Line 5,541 ⟶ 6,306:
lemma "inorder example = [7, 4, 2, 5, 1, 8, 6, 9, 3]" by code_simp
fun postorder :: "'a tree
"postorder Leaf = []"
| "postorder (Node l a r) = postorder l @ postorder r @ [a]"
Line 5,561 ⟶ 6,326:
so we provide some help by defining what the size of a tree is.
›
fun tree_size :: "'a tree
"tree_size Leaf = 1"
| "tree_size (Node l _ r) = 1 + tree_size l + tree_size r"
function (sequential) bfs :: "'a tree list
"bfs [] = []"
| "bfs (Leaf#q) = bfs q"
Line 5,571 ⟶ 6,336:
by pat_completeness auto
termination bfs
by(relation "measure (
fun levelorder :: "'a tree
"levelorder t = bfs [t]"
lemma "levelorder example = [1, 2, 3, 4, 5, 6, 7, 8, 9]" by code_simp
end</
=={{header|J}}==
<
postorder=: ([:; postorder&.>@}.) , >@{.
levelorder=: ;@({::L:1 _~ [: (/: #@>) <S:1@{::)
inorder=: ([:; inorder&.>@(''"_`(1&{)@.(1<#))) , >@{. , [:; inorder&.>@}.@}.</
Required example:
<
N1=: adverb def '(<m),<y'
L=: adverb def '<m'
tree=: 1 N2 (2 N2 (4 N1 (7 L)) 5 L) 3 N1 6 N2 (8 L) 9 L</
This tree is organized in a pre-order fashion
<
1 2 4 7 5 3 6 8 9</
post-order is not that much different from pre-order, except that the children must extracted before the parent.
<
7 4 5 2 8 9 6 3 1</
Implementing in-order is more complex because we must sometimes test whether we have any leaves, instead of relying on J's implicit looping over lists
<
7 4 2 5 1 8 6 9 3</
level-order can be accomplished by constructing a map of the locations of the leaves, sorting these map locations by their non-leaf indices and using the result to extract all leaves from the tree. Elements at the same level with the same parent will have the same sort keys and thus be extracted in preorder fashion, which works just fine.
<
1 2 3 4 5 6 7 8 9</
For J novices, here's the tree instance with a few redundant parenthesis:
<
Syntactically, N2 is a binary node expressed as <code>m N2 n y</code>. N1 is a node with a single child, expressed as <code>m N2 y</code>. L is a leaf node, expressed as <code>m L</code>. In all three cases, the parent value (<code>m</code>) for the node appears on the left, and the child tree(s) appear on the right. (And <code>n</code> must be parenthesized if it is not a single word.)
Line 5,626 ⟶ 6,391:
Of course, there are other ways of representing tree structures in J. One fairly natural approach pairs a list of data with a matching list of parent indices. For example:
<
Here, we have two possible ways of identifying the root node. It can be in a known place in the list (index 0, for this example). But it is also the only node which is its own parent. For this task we'll use the more general (and thus slower) approach which allows us to place the root node anywhere in the sequence.
Line 5,632 ⟶ 6,397:
Next, let's define a few utilities:
<
reorder=:4 :0
Line 5,644 ⟶ 6,409:
parent=:3 :'parent[''data parent''=. y'
childinds=: [: <:@(2&{.@-.&> #\) (</. #\)`(]~.)`(a:"0)}~</
Here, <code>data</code> extracts the list of data items from the tree and <code>parent</code> extracts the structure from the tree.
Line 5,656 ⟶ 6,421:
Next, we define our "traversal" routines (actually, we are going a bit overboard here - we really only need to extract the data for this tasks's concept of traversal):
<
levelorder=: /:@depth@parent reorder ]
Line 5,708 ⟶ 6,473:
todo=. todo,|.ch end. end.
r
)</
These routines assume that children of a node are arranged so that the lower index appears to the left of the higher index. If instead we wanted to rely on the ordering of their values, we could first use <code>dataorder</code> to enforce the assumption that child indexes are ordered properly.
Line 5,714 ⟶ 6,479:
Example use:
<
1 2 3 4 5 6 7 8 9
0 0 0 1 1 2 3 5 5
Line 5,725 ⟶ 6,490:
postorder dataorder example
7 4 5 2 8 9 6 3 1
1 3 3 8 6 6 7 8 8</
(Once again, all we really need for this task is the first row of those results - the part that represents data.)
Line 5,737 ⟶ 6,502:
{{works with|Java|1.5+}}
<
public class TreeTraversal {
Line 5,823 ⟶ 6,588:
}
}</
Output:
<pre>1 2 4 7 5 3 6 8 9
Line 5,838 ⟶ 6,603:
{{works with|Java|1.8+}}
<
import java.util.Queue;
import java.util.LinkedList;
Line 5,963 ⟶ 6,728:
System.out.println();
}
}</
Output:
Line 5,975 ⟶ 6,740:
====Iteration====
inspired by [[#Ruby|Ruby]]
<
this.value = value;
this.left = left;
Line 6,014 ⟶ 6,779:
print("*** inorder ***"); tree.inorder(print);
print("*** postorder ***"); tree.postorder(print);
print("*** levelorder ***"); tree.levelorder(print);</
====Functional composition====
Line 6,020 ⟶ 6,785:
(for binary trees consisting of nested lists)
<
function preorder(n) {
Line 6,108 ⟶ 6,873:
return wikiTable(lstTest, true) + '\n\n' + JSON.stringify(lstTest);
})();</
Output:
Line 6,125 ⟶ 6,890:
|}
<
["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]],["levelorder",[1,2,3,4,5,6,7,8,9]]]</
Line 6,137 ⟶ 6,902:
<
'use strict';
Line 6,257 ⟶ 7,022:
}, {});
})();</
{{Out}}
<
"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]}</
===ES6===
Line 6,268 ⟶ 7,033:
{{Trans|Haskell}}
{{Trans|Python}}
<
"use strict";
Line 6,314 ⟶ 7,079:
// task: 'Visualize a tree'
console.log([
"
"
"
" 1
"
"
"
].join("\n"));
Line 6,395 ⟶ 7,160:
// MAIN ---
return main();
})();</
{{Out}}
<pre>
1
preorder: 1,2,4,7,5,3,6,8,9
inorder: 7,4,2,5,1,8,6,9,3
Line 6,413 ⟶ 7,178:
The implementation assumes an array structured recursively as [ node, left, right ], where "left" and "right" may be [] or null equivalently.
<
if length == 0 then empty
else .[0], (.[1]|preorder), (.[2]|preorder)
Line 6,439 ⟶ 7,204:
def levelorder: [.] | recurse( tails ) | heads;
</syntaxhighlight>
'''The task''':
<
# [node, left, right]
def atree: [1, [2, [4, [7,[],[]],
Line 6,457 ⟶ 7,222:
;
task</
{{Out}}
$ jq -n -c -r -f Tree_traversal.jq
Line 6,466 ⟶ 7,231:
=={{header|Julia}}==
<
Any[]],
Any[]],
Line 6,492 ⟶ 7,257:
t = mapreduce(x -> isa(x, Number) ? (f(x); []) : x, vcat, t)
end
</syntaxhighlight>
{{Out}}
Line 6,507 ⟶ 7,272:
=={{header|Kotlin}}==
===procedural style===
<
override fun toString() = "$v"
}
Line 6,573 ⟶ 7,338:
exec(" postOrder: ", nodes[1], ::postOrder)
exec("level-order: ", nodes[1], ::levelOrder)
}</
{{Out}}
Line 6,584 ⟶ 7,349:
===object-oriented style===
<
data class Node(val v: Int, var left: Node? = null, var right: Node? = null) {
override fun toString() = " $v"
Line 6,625 ⟶ 7,390:
exec("level-order:", Node::levelOrder)
}
}</
=={{header|Lambdatalk}}==
Line 6,638 ⟶ 7,403:
- {A.get index array} gets the value of array at index
</pre>
<
{def walk
Line 6,673 ⟶ 7,438:
{sort < {T}} -> 1 2 3 4 5 6 7 8 9
{sort > {T}} -> 9 8 7 6 5 4 3 2 1
</syntaxhighlight>
=={{header|Lingo}}==
<
property _val, _left, _right
Line 6,703 ⟶ 7,468:
on getRight (me)
return me._right
end</
<
on inOrder (me, node, l)
Line 6,755 ⟶ 7,520:
delete the last char of str
return str
end</
Usage:
<
l = []
repeat with i = 1 to 10
Line 6,777 ⟶ 7,542:
put "inorder: " & trav.serialize(trav.inOrder(l[1]))
put "postorder: " & trav.serialize(trav.postOrder(l[1]))
put "level-order: " & trav.serialize(trav.levelOrder(l[1]))</
{{Out}}
Line 6,788 ⟶ 7,553:
=={{header|Logo}}==
<
to node.left :node
Line 6,844 ⟶ 7,609:
in.order :tree [(type ? "| |)] (print)
post.order :tree [(type ? "| |)] (print)
level.order :tree [(type ? "| |)] (print)</
=={{header|Logtalk}}==
<
:- object(tree_traversal).
Line 6,928 ⟶ 7,693:
:- end_object.
</syntaxhighlight>
Sample output:
<
| ?- ?- tree_traversal::orders.
Pre-order: 1 2 4 7 5 3 6 8 9
Line 6,937 ⟶ 7,702:
Level-order: 1 2 3 4 5 6 7 8 9
yes
</syntaxhighlight>
=={{header|Lua}}==
<syntaxhighlight lang="lua">
local function
if type(tr[val]) == "table" then
depth_first(tr[val], a, b, c, flat_list)
elseif type(tr[val]) ~= "nil" then
table.insert(flat_list, tr[val])
end -- if
end -- for
return flat_list
end
local function flatten_pre_order(tr) return depth_first(tr, 1, 2, 3, {}) end
local function flatten_in_order(tr) return depth_first(tr, 2, 1, 3, {}) end
local function flatten_post_order(tr) return depth_first(tr, 2, 3, 1, {}) end
local function flatten_level_order(tr)
local flat_list, queue = {}, {tr}
while next(queue) do -- while queue is not empty
local node = table.remove(queue, 1) -- dequeue
if
table.insert(flat_list, node[1])
table.insert(queue, node[2]) -- enqueue
table.insert(queue, node[3]) -- enqueue
else
table.insert(flat_list, node)
end -- if
end -- while
return flat_list
end
-- Example
local tree =
print("
print("
print("
print("
</syntaxhighlight>
=={{header|M2000 Interpreter}}==
Line 6,991 ⟶ 7,747:
A tuple is an "auto array" in M2000 Interpreter. (,) is the zero length array.
<syntaxhighlight lang="m2000 interpreter">
Module CheckIt {
Null=(,)
Line 7,051 ⟶ 7,807:
}
CheckIt
</syntaxhighlight>
===Using OOP===
Now tree is nodes with pointers to nodes (a node ifs a Group, the user object)
The "as pointer" is optional, but we can use type check if we want.
<syntaxhighlight lang="m2000 interpreter">
Module OOP {
\\ Class is a global function (until this module end)
Line 7,140 ⟶ 7,896:
}
OOP
</syntaxhighlight>
or we can put modules inside Node Class as methods
also i put a visitor as a call back (a lambda function called as module)
<syntaxhighlight lang="m2000 interpreter">
Module OOP {
\\ Class is a global function (until this module end)
Line 7,232 ⟶ 7,988:
}
OOP
</syntaxhighlight>
Using Event object as visitor
<syntaxhighlight lang="m2000 interpreter">
Module OOP {
\\ Class is a global function (until this module end)
Line 7,327 ⟶ 8,083:
}
OOP
</syntaxhighlight>
{{out}}
Line 7,338 ⟶ 8,094:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
preorder[a_[b__]] := Flatten@{a, preorder /@ {b}};
inorder[a_Integer] := a;
Line 7,346 ⟶ 8,102:
levelorder[a_] :=
Flatten[Table[Level[a, {n}], {n, 0, Depth@a}]] /. {b_Integer[__] :>
b};</
Example:
<
inorder[1[2[4[7], 5], 3[6[8, 9]]]]
postorder[1[2[4[7], 5], 3[6[8, 9]]]]
levelorder[1[2[4[7], 5], 3[6[8, 9]]]]</
{{out}}
<pre>{1, 2, 4, 7, 5, 3, 6, 8, 9}
Line 7,360 ⟶ 8,116:
=={{header|Mercury}}==
<
:- interface.
Line 7,452 ⟶ 8,208:
print_value(V, !IO) :-
io.print(V, !IO),
io.write_string(" ", !IO).</
Output:
<pre>preorder: 1 2 4 7 5 3 6 8 9
Line 7,458 ⟶ 8,214:
postorder: 7 4 5 2 8 9 6 3 1
levelorder: 1 2 3 4 5 6 7 8 9 </pre>
=={{header|Miranda}}==
<syntaxhighlight lang="miranda">main :: [sys_message]
main = [Stdout (lay [show (f example)
| f <- [preorder,inorder,postorder,levelorder]])]
example :: tree num
example = Node 1 (Node 2 (Node 4 (leaf 7) Nilt)
(leaf 5))
(Node 3 (Node 6 (leaf 8) (leaf 9)) Nilt)
tree * ::= Nilt | Node * (tree *) (tree *)
leaf :: *->tree *
leaf k = Node k Nilt Nilt
preorder :: tree *->[*]
preorder Nilt = []
preorder (Node v l r) = v : preorder l ++ preorder r
inorder :: tree *->[*]
inorder Nilt = []
inorder (Node v l r) = inorder l ++ v : inorder r
postorder :: tree *->[*]
postorder Nilt = []
postorder (Node v l r) = postorder l ++ postorder r ++ [v]
levelorder :: tree *->[*]
levelorder t = f [t]
where f [] = []
f (Nilt:xs) = f xs
f (Node v l r:xs) = v : f (xs++[l,r])</syntaxhighlight>
{{out}}
<pre>[1,2,4,7,5,3,6,8,9]
[7,4,2,5,1,8,6,9,3]
[7,4,5,2,8,9,6,3,1]
[1,2,3,4,5,6,7,8,9]</pre>
=={{header|Nim}}==
<
type
Line 7,504 ⟶ 8,298:
echo inorder tree
echo postorder tree
echo levelorder tree</
{{out}}
Line 7,513 ⟶ 8,307:
=={{header|Objeck}}==
<
class Test {
Line 7,626 ⟶ 8,420:
}
}
</syntaxhighlight>
Output:
Line 7,637 ⟶ 8,431:
=={{header|OCaml}}==
<
| Node of 'a * 'a tree * 'a tree
Line 7,686 ⟶ 8,480:
inorder (Printf.printf "%d ") tree; print_newline ();
postorder (Printf.printf "%d ") tree; print_newline ();
levelorder (Printf.printf "%d ") tree; print_newline ()</
Output:
<pre>1 2 4 7 5 3 6 8 9
Line 7,695 ⟶ 8,489:
=={{header|Oforth}}==
<
Tree method: initialize(v, l, r) v := v l := l r := r ;
Line 7,725 ⟶ 8,519:
n l dup ifNotNull: [ c send ] drop
n r dup ifNotNull: [ c send ] drop
] ;</
{{out}}
Line 7,748 ⟶ 8,542:
=={{header|ooRexx}}==
<syntaxhighlight lang="oorexx">
one = .Node~new(1);
two = .Node~new(2);
Line 7,832 ⟶ 8,626:
nodequeue~queue(next~right)
end
</syntaxhighlight>
Output:
<pre>
Line 7,842 ⟶ 8,636:
=={{header|Oz}}==
<
Tree = n(1
n(2
Line 7,899 ⟶ 8,693:
{Show {Inorder Tree}}
{Show {Postorder Tree}}
{Show {Levelorder Tree}}</
=={{header|PascalABC.NET}}==
<syntaxhighlight lang="delphi">
type
Node<T> = auto class
data: T;
left,right: Node<T>;
end;
function ND<T>(data: T; left: Node<T> := nil; right: Node<T> := nil)
:= new Node<T>(data,left,right);
procedure Prefix<T>(r: Node<T>);
begin
if r = nil then
exit;
Print(r.data);
Prefix(r.left);
Prefix(r.right);
end;
procedure Infix<T>(r: Node<T>);
begin
if r = nil then
exit;
Infix(r.left);
Print(r.data);
Infix(r.right);
end;
procedure Postfix<T>(r: Node<T>);
begin
if r = nil then
exit;
Postfix(r.left);
Postfix(r.right);
Print(r.data);
end;
procedure LevelOrder<T>(r: Node<T>);
begin
if r = nil then
exit;
var q := new Queue<Node<T>>;
q.Enqueue(r);
while q.Count > 0 do
begin
var x := q.Dequeue;
Print(x.data);
if x.left <> nil then
q.Enqueue(x.Left);
if x.Right <> nil then
q.Enqueue(x.Right);
end;
end;
begin
var root := ND(1,ND(2,ND(4,ND(7)),ND(5)),ND(3,ND(6,ND(8),ND(9))));
Println(root);
Prefix(root); Println;
Infix(root); Println;
Postfix(root); Println;
LevelOrder(root); Println;
end.
</syntaxhighlight>
{{out}}
<pre>
(1,(2,(4,(7,nil,nil),nil),(5,nil,nil)),(3,(6,(8,nil,nil),(9,nil,nil)),nil))
1 2 4 7 5 3 6 8 9
7 4 2 5 1 8 6 9 3
7 4 5 2 8 9 6 3 1
1 2 3 4 5 6 7 8 9
</pre>
=={{header|Perl}}==
Tree nodes are represented by 3-element arrays: [0] - the value; [1] - left child; [2] - right child.
<
{
my $t = shift or return ();
Line 7,938 ⟶ 8,806:
print "in: @{[inorder($x)]}\n";
print "post: @{[postorder($x)]}\n";
print "depth: @{[depth($x)]}\n";</
Output:
<pre>pre: 1 2 4 7 5 3 6 8 9
Line 7,950 ⟶ 8,818:
This is included in the distribution as demo\rosetta\Tree_traversal.exw, which also contains a way to build such a nested structure, and thirdly a "flat list of nodes" tree, that allows more interesting options such as a tag sort.
<!--<
<span style="color: #008080;">constant</span> <span style="color: #000000;">VALUE</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">LEFT</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">RIGHT</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">3</span>
Line 7,997 ⟶ 8,865:
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n postorder: "</span><span style="color: #0000FF;">)</span> <span style="color: #000000;">postorder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n level-order: "</span><span style="color: #0000FF;">)</span> <span style="color: #000000;">level_order</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
Line 8,008 ⟶ 8,876:
=={{header|PHP}}==
<
private $left;
private $right;
Line 8,109 ⟶ 8,977:
$tree->postOrder($arr[1]);
echo "\nlevel-order:\t";
$tree->levelOrder($arr[1]);</
Output:
<pre>preorder: 1 2 4 7 5 3 6 8 9
Line 8,117 ⟶ 8,985:
=={{header|PicoLisp}}==
<
(when Node
(Fun (car Node))
Line 8,150 ⟶ 9,018:
(prin (align -13 (pack Order ":")))
(Order *Tree printsp)
(prinl) )</
Output:
<pre>preorder: 1 2 4 7 5 3 6 8 9
Line 8,159 ⟶ 9,027:
=={{header|Prolog}}==
Works with SWI-Prolog.
<
Tree= [1,
[2,
Line 8,215 ⟶ 9,083:
append_dl(X-Y, Y-Z, X-Z).
</syntaxhighlight>
Output :
<pre>?- tree.
Line 8,227 ⟶ 9,095:
=={{header|PureBasic}}==
{{works with|PureBasic|4.5+}}
<
value.i
*left.node
Line 8,361 ⟶ 9,229:
Input()
CloseConsole()
EndIf</
Sample output:
<pre>preorder: 1 2 4 7 5 3 6 8 9
Line 8,372 ⟶ 9,240:
===Python: Procedural===
<
Node = namedtuple('Node', 'data, left, right')
Line 8,443 ⟶ 9,311:
print(f"{traversal.__name__:>{w}}:", end=' ')
traversal(tree)
print()</
'''Sample output:'''
Line 8,459 ⟶ 9,327:
Subclasses a namedtuple adding traversal methods that apply a visitor function to data at nodes of the tree in order
<
from sys import stdout
Line 8,519 ⟶ 9,387:
stdout.write('\nlevelorder: ')
tree.levelorder(printwithspace)
stdout.write('\n')</
{{out}}
Line 8,536 ⟶ 9,404:
This level of abstraction and reuse brings real efficiencies – the short and easily-written '''foldTree''', for example, doesn't just traverse and list contents in flexible orders - we can pass any kind of accumulation or tree-transformation to it.
<
from itertools import chain
Line 8,746 ⟶ 9,614:
if __name__ == '__main__':
main()</
{{Out}}
<pre>Tree traversals - accumulating and folding:
Line 8,763 ⟶ 9,631:
=={{header|Qi}}==
<syntaxhighlight lang="qi">
(set *tree* [1 [2 [4 [7]]
[5]]
Line 8,808 ⟶ 9,676:
(inorder (value *tree*))
(levelorder (value *tree*))
</syntaxhighlight>
Output:
Line 8,820 ⟶ 9,688:
Requires the words at [[Queue/Definition#Quackery]] for <code>level-order</code>.
<
[ ' [ 1
Line 8,866 ⟶ 9,734:
tree in-order cr
tree post-order cr
tree level-order cr</
{{out}}
Line 8,877 ⟶ 9,745:
=={{header|Racket}}==
<
#lang racket
Line 8,900 ⟶ 9,768:
(define (run order)
(printf "~a:" (object-name order))
(order the-tree (
(newline))
(for-each run (list preorder inorder postorder levelorder))
</syntaxhighlight>
Output:
Line 8,915 ⟶ 9,783:
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku"
has TreeNode $.parent;
has TreeNode $.left;
Line 8,972 ⟶ 9,840:
say "inorder: ",$root.in-order.join(" ");
say "postorder: ",$root.post-order.join(" ");
say "levelorder:",$root.level-order.join(" ");</
{{out}}
<pre>preorder: 1 2 4 7 5 3 6 8 9
Line 8,980 ⟶ 9,848:
=={{header|REBOL}}==
<syntaxhighlight lang="rebol">
tree: [1 [2 [4 [7 [] []] []] [5 [] []]] [3 [6 [8 [] []] [9 [] []]] []]]
; "compacted" version
Line 9,027 ⟶ 9,895:
]
prin "level-order: " level-order tree
</syntaxhighlight>
{{out}}
<pre>
Line 9,035 ⟶ 9,903:
level-order: 1 2 3 4 5 6 7 8 9
</pre>
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
= <Show Preorder <Tree>>
<Show Inorder <Tree>>
<Show Postorder <Tree>>
<Show Levelorder <Tree>>;
};
Show {
s.F t.T = <Prout s.F ': ' <Mu s.F t.T>>;
};
Tree {
= (1 (2 (4 (7 () ()) ()) (5 () ())) (3 (6 (8 () ()) (9 () ())) ()));
};
Preorder {
() = ;
(s.V t.L t.R) = s.V <Preorder t.L> <Preorder t.R>;
};
Inorder {
() = ;
(s.V t.L t.R) = <Inorder t.L> s.V <Inorder t.R>;
};
Postorder {
() = ;
(s.V t.L t.R) = <Postorder t.L> <Postorder t.R> s.V;
};
Levelorder {
= ;
() e.Q = <Levelorder e.Q>;
(s.V t.L t.R) e.Q = s.V <Levelorder e.Q t.L t.R>;
};</syntaxhighlight>
{{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
Levelorder : 1 2 3 4 5 6 7 8 9</pre>
=={{header|REXX}}==
<
/* REXX ***************************************************************
* Tree traversal
Line 9,355 ⟶ 10,265:
Say ''
End
Return</
{{out}}
<pre> 1
Line 9,371 ⟶ 10,281:
=={{header|Ruby}}==
<
def self.from_array(nested_list)
value, left, right = nested_list
Line 9,410 ⟶ 10,320:
root.send(mthd) {|node| print "#{node.value} "}
puts
end</
{{out}}
Line 9,421 ⟶ 10,331:
=={{header|Rust}}==
This solution uses iteration (rather than recursion) for all traversal types.
<syntaxhighlight lang="rust">
#![feature(box_syntax, box_patterns)]
Line 9,488 ⟶ 10,398:
}
//
fn iterative_inorder(&self) -> Vec<&TreeNode<T>> {
let mut stack: Vec<&TreeNode<T>> = Vec::new();
let mut res: Vec<&TreeNode<T>> = Vec::new();
let mut
}
!stack.is_empty()
} {
let tree = stack.pop().unwrap();
res.push(tree);
opt = tree.right.as_deref();
}
res
Line 9,597 ⟶ 10,492:
}
}
</syntaxhighlight>
Output is same as Ruby et al.
=={{header|Scala}}==
{{works with|Scala|2.11.x}}
<
def preorder(f: IntNode => Unit) {
Line 9,656 ⟶ 10,551:
println(s)
}
}</
Output:<pre>
Line 9,666 ⟶ 10,561:
=={{header|Scheme}}==
<
(if (null? tree)
'()
Line 9,731 ⟶ 10,626:
())))
(demonstration the-task-tree)</
{{out}}
<pre>preorder: 1 2 4 7 5 3 6 8 9
Line 9,739 ⟶ 10,634:
=={{header|SequenceL}}==
<syntaxhighlight lang="sequencel">
main(args(2)) :=
"preorder: " ++ toString(preOrder(testTree)) ++
Line 9,782 ⟶ 10,677:
)
);
</syntaxhighlight>
{{out}}
Output:
Line 9,791 ⟶ 10,686:
level-order: [1,2,3,4,5,6,7,8,9]
</pre>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program tree_traversal;
tree := [1, [2, [4, [7]], [5]], [3, [6, [8], [9]]]];
print("preorder ", preorder(tree));
print("inorder ", inorder(tree));
print("postorder ", postorder(tree));
print("level-order ", levelorder(tree));
proc preorder(tree);
if tree = om then return []; end if;
[item, left, right] := tree;
return [item] + preorder(left) + preorder(right);
end proc;
proc inorder(tree);
if tree = om then return []; end if;
[item, left, right] := tree;
return inorder(left) + [item] + inorder(right);
end proc;
proc postorder(tree);
if tree = om then return []; end if;
[item, left, right] := tree;
return postorder(left) + postorder(right) + [item];
end proc;
proc levelorder(tree);
items := [];
loop init queue := [tree]; while queue /= [] do
[item, left, right] fromb queue;
items with:= item;
if left /= om then queue with:= left; end if;
if right /= om then queue with:= right; end if;
end loop;
return items;
end proc;
end program;</syntaxhighlight>
{{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|Sidef}}==
{{trans|Perl}}
<
t ? [t[0], __FUNC__(t[1])..., __FUNC__(t[2])...] : [];
}
Line 9,821 ⟶ 10,760:
say "in: #{inorder(x)}";
say "post: #{postorder(x)}";
say "depth: #{depth(x)}";</
{{out}}
<pre>
Line 9,840 ⟶ 10,779:
'''Object subclass: EmptyNode'''
<
EmptyNode>>accept: aVisitor
Line 9,849 ⟶ 10,788:
EmptyNode>>traverse: aVisitorClass do: aBlock
^self accept: (aVisitorClass block: aBlock)
</syntaxhighlight>
'''EmptyNode subclass: Node'''
<
Node>>accept: aVisitor
^aVisitor visit: self
Line 9,887 ⟶ 10,826:
Node class>>data: anObject
^self new data: anObject
</syntaxhighlight>
'''Object subclass: Visitor'''
<
visit: aNode
self subclassResponsibility
Line 9,907 ⟶ 10,846:
Visitor class>>block: aBlock
^self new block: aBlock
</syntaxhighlight>
'''Visitor subclass: InOrder'''
<
InOrder>>visit: aNode
aNode left accept: self.
block value: aNode.
aNode right accept: self
</syntaxhighlight>
'''Visitor subclass: LevelOrder'''
<
LevelOrder>>visit: aNode
| queue |
Line 9,930 ⟶ 10,869:
add: aNode right;
yourself
</syntaxhighlight>
'''Visitor subclass: PostOrder'''
<
PostOrder>>visit: aNode
aNode left accept: self.
aNode right accept: self.
block value: aNode
</syntaxhighlight>
"Visitor subclass: PreOrder"
<
PreOrder>>visit: aNode
block value: aNode.
aNode left accept: self.
aNode right accept: self
</syntaxhighlight>
Execute code in a Workspace:
<
tree := (Node data: 1)
left: ((Node data: 2)
Line 9,967 ⟶ 10,906:
tree traverse: LevelOrder do: [:node | Transcript print: node data; space].
Transcript cr.
</syntaxhighlight>
Output in Transcript:
Line 9,976 ⟶ 10,915:
=={{header|Swift}}==
<
let value: T
let left: TreeNode?
Line 10,061 ⟶ 11,000:
print("level-order: ", terminator: "")
n.levelOrder(function: fn)
print()</
{{out}}
Line 10,073 ⟶ 11,012:
=={{header|Tcl}}==
{{works with|Tcl|8.6}} or {{libheader|TclOO}}
<
# Basic tree data structure stuff...
variable val l r
Line 10,122 ⟶ 11,061:
}
}
}</
Note that in Tcl it is conventional to handle performing something “for each element” by evaluating a script in the caller's scope for each node after setting a caller-nominated variable to the value for that iteration. Doing this transparently while recursing requires the use of a varying ‘level’ parameter to <code>upvar</code> and <code>uplevel</code>, but makes for compact and clear code.
Demo code to satisfy the official challenge instance:
<
proc Tree nested {
lassign $nested v l r
Line 10,147 ⟶ 11,086:
puts "postorder: [Listify $t postorder]"
puts "level-order: [Listify $t levelorder]"
$t destroy</
Output:
<pre>preorder: 1 2 4 7 5 3 6 8 9
Line 10,156 ⟶ 11,095:
=={{header|UNIX Shell}}==
Bash (also "sh" on most Unix systems) has arrays. We implement a node as an association between three arrays: left, right, and value.
<
right=()
value=()
Line 10,239 ⟶ 11,178:
inorder 1
postorder 1
levelorder 1</
The output:
<
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</
=={{header|Ursala}}==
Line 10,256 ⟶ 11,195:
the result on standard output as a
list of lists of naturals.
<
1^:<
Line 10,269 ⟶ 11,208:
#cast %nLL
main = <.pre,in,post,lev> tree</
output:
<pre>
Line 10,281 ⟶ 11,220:
=={{header|VBA}}==
TreeItem Class Module
<syntaxhighlight lang="vb">
Public Value As Integer
Public LeftChild As TreeItem
Public RightChild As TreeItem
</syntaxhighlight>
Module
<syntaxhighlight lang="vb">
Dim tihead As TreeItem
Line 10,359 ⟶ 11,298:
Call LevelOrder(tihead)
End Sub
</syntaxhighlight>
{{out}}
<pre>
Line 10,367 ⟶ 11,306:
level-order: 1 2 3 4 5 6 7 8 9
</pre>
=={{header|VBScript}}==
<syntaxhighlight lang="vb">
' 1
' / \
' / \
' / \
' 2 3
' / \ /
' 4 5 6
' / / \
' 7 8 9
'with no pointers available, the binary tree has to be saved in an array
' root at index 1
' parent index is i\2
' children indexes are i*2 and i*2+1
' a value of 0 denotes an empty branch
Sub print(s):
On Error Resume Next
WScript.stdout.Write(s)
If err= &h80070006& Then WScript.Echo " Please run this script with CScript": WScript.quit
End Sub
Sub inorder(i)
If tree(i*2)<>0 Then inorder(i*2)
print tree(i)& vbtab
If tree(i*2+1)<>0 Then inorder(i*2+1)
End Sub
Sub preorder(i)
print tree(i)& vbtab
If tree(i*2)<>0 Then preorder(i*2)
If tree(i*2+1)<>0 Then preorder(i*2+1)
End Sub
Sub postorder(i)
If tree(i*2)<>0 Then postorder(i*2)
If tree(i*2+1)<>0 Then postorder(i*2+1)
print tree(i)& vbTab
End Sub
Sub levelorder(x)
Dim i
For i= 1 To UBound(tree)
If tree(i)<>0 Then print tree(i)& vbTab
Next
End sub
Dim tree
' 1 2 3 4 5 6 7 8 9 1011121314151617181920212223242526
' 1 2 2 3 3 3 3 4 4 4 4 4 4 4 4
tree=Array(0,1,2,3,4,5,6,0,7,0,0,0,8,9,0,0,0,0,0,0,0,0,0,0,0,0,0,0)
print vbCrLf & "Preorder" & vbcrlf
preorder(1)
print vbCrLf & "Inorder" & vbcrlf
inorder(1)
print vbCrLf & "Postorder" & vbcrlf
postorder(1)
print vbCrLf & "Levelorder" & vbcrlf
levelorder(1)
</syntaxhighlight>
{{out}}
<small>
<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
Levelorder
1 2 3 4 5 6 7 8 9
</pre>
</small>
=={{header|Wren}}==
{{trans|Kotlin}}
The object-oriented version.
<
construct new(v) {
_v = v
Line 10,437 ⟶ 11,453:
nodes[1].exec(" inOrder:", Fn.new { |n| n.inOrder() })
nodes[1].exec(" postOrder:", Fn.new { |n| n.postOrder() })
nodes[1].exec("level-order:", Fn.new { |n| n.levelOrder() })</
{{out}}
Line 10,445 ⟶ 11,461:
postOrder: 7 4 5 2 8 9 6 3 1
level-order: 1 2 3 4 5 6 7 8 9
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang "XPL0">def \Node\ Left, Data, Right;
proc PreOrder(Node); \Traverse tree at Node in preorder
int Node;
[if Node # 0 then
[IntOut(0, Node(Data)); ChOut(0, ^ );
PreOrder(Node(Left));
PreOrder(Node(Right));
];
];
proc InOrder(Node); \Traverse tree at Node in inorder
int Node;
[if Node # 0 then
[InOrder(Node(Left));
IntOut(0, Node(Data)); ChOut(0, ^ );
InOrder(Node(Right));
];
];
proc PostOrder(Node); \Traverse tree at Node in postorder
int Node;
[if Node # 0 then
[PostOrder(Node(Left));
PostOrder(Node(Right));
IntOut(0, Node(Data)); ChOut(0, ^ );
];
];
proc LevelOrder(Node); \Traverse tree at Node in level-order
int Node;
def S=100*3; \size of queue (must be a multiple of 3 for wrap-around)
int Q(S), \queue (FIFO)
F, E; \fill and empty indexes
proc EnQ(Node); \Enqueue Node
int Node;
[Q(F):= Node(Left); F:= F+1;
Q(F):= Node(Data); F:= F+1;
Q(F):= Node(Right); F:= F+1;
if F >= S then F:= 0;
];
proc DeQ; \Dequeue Node
[Node(Left):= Q(E); E:= E+1;
Node(Data):= Q(E); E:= E+1;
Node(Right):= Q(E); E:= E+1;
if E >= S then E:= 0;
];
[F:= 0; E:= 0; \empty queue
EnQ(Node);
while E # F do
[DeQ;
IntOut(0, Node(Data)); ChOut(0, ^ );
if Node(Left) # 0 then
EnQ(Node(Left));
if Node(Right) # 0 then
EnQ(Node(Right));
];
];
int Tree;
[Tree:= [[ [[0,7,0],4,0], 2, [0,5,0]], 1, [ [[0,8,0], 6, [0,9,0]], 3, 0 ]];
Text(0, "preorder: "); PreOrder(Tree); CrLf(0);
Text(0, "inorder: "); InOrder(Tree); CrLf(0);
Text(0, "postorder: "); PostOrder(Tree); CrLf(0);
Text(0, "level-order: "); LevelOrder(Tree); CrLf(0);
]</syntaxhighlight>
{{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|zkl}}==
<
fcn init(val,[Node]l=Void,[Node]r=Void) { v,left,right=vm.arglist }
}
Line 10,478 ⟶ 11,572:
sink
}
}</
It is easy to convert to lazy by replacing "sink.write" with "vm.yield" and wrapping the traversal with a Utils.Generator.
<
Node(2,
Node(4,Node(7)),
Line 10,490 ⟶ 11,584:
t.inOrder() .apply("v").println(" inorder");
t.postOrder() .apply("v").println(" postorder");
t.levelOrder().apply("v").println(" level-order");</
The "apply("v")" extracts the contents of var v from each node.
{{out}}
|