Tree traversal: Difference between revisions
Content deleted Content added
Not a robot (talk | contribs) Add Miranda |
PascalABC.NET |
||
(19 intermediate revisions by 9 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,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>
Line 4,818 ⟶ 5,556:
</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,924 ⟶ 8,694:
{Show {Postorder Tree}}
{Show {Levelorder Tree}}</syntaxhighlight>
=={{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}}==
Line 9,059 ⟶ 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}}==
Line 9,512 ⟶ 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,815 ⟶ 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}}==
Line 10,472 ⟶ 11,387:
{{trans|Kotlin}}
The object-oriented version.
<syntaxhighlight lang="
construct new(v) {
_v = v
|