Tree traversal: Difference between revisions
m
→{{header|11l}}: Void
Antoni Gual (talk | contribs) |
Alextretyak (talk | contribs) m (→{{header|11l}}: Void) |
||
| (17 intermediate revisions by 7 users not shown) | |||
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 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}}==
Line 2,318 ⟶ 2,630:
&
)</syntaxhighlight>
=={{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}}==
Line 3,527 ⟶ 3,912:
[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}}==
Line 3,577 ⟶ 4,156:
levelOrder(btree, fn v { print(" ", v) })
println()</syntaxhighlight>
=={{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,762 ⟶ 4,425:
=={{header|Elena}}==
ELENA
<syntaxhighlight lang="elena">import extensions;
import extensions'routines;
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 4,818 ⟶ 5,481:
</pre>
=={{header|
{{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}}==
Line 7,444 ⟶ 8,139:
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}}==
Line 9,021 ⟶ 9,754:
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}}==
Line 9,777 ⟶ 10,552:
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}}==
Line 10,434 ⟶ 11,253:
{{trans|Kotlin}}
The object-oriented version.
<syntaxhighlight lang="
construct new(v) {
_v = v
Line 10,508 ⟶ 11,327:
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>
| |||