Rosetta Code

Tree traversal: Difference between revisions

Page Discussion

Tree traversal (view source)

Revision as of 08:39, 7 May 2024

9,747 bytes added ,  24 days ago
m
→‎{{header|11l}}: Void
(Add 8080 Assembly)
(12 intermediate revisions by 6 users not shown)
Line 44:
.right = right
 
F preorder(visitor) -> NVoid
visitor(.data)
I .left != N
Line 51:
.right.preorder(visitor)
 
F inorder(visitor) -> NVoid
I .left != N
.left.inorder(visitor)
Line 58:
.right.inorder(visitor)
 
F postorder(visitor) -> NVoid
I .left != N
.left.postorder(visitor)
Line 65:
visitor(.data)
 
F preorder2(&d, level = 0) -> NVoid
d[level].append(.data)
I .left != N
Line 300:
 
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
Line 3,791 ⟶ 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}}==
Line 3,924 ⟶ 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 4,109 ⟶ 4,425:
 
=={{header|Elena}}==
ELENA 56.0x :
<syntaxhighlight lang="elena">import extensions;
import extensions'routines;
Line 4,122 ⟶ 4,438:
class Node
{
rprop int Value : rprop;
rprop Node Left : rprop;
rprop Node Right : rprop;
constructor new(int value)
Line 4,188 ⟶ 4,504:
LevelOrder = new Enumerable
{
Queue<Node> queue := class Queue<Node>.allocate(4).push:(self);
Enumerator enumerator() = new Enumerator
Line 4,194 ⟶ 4,510:
bool next() = queue.isNotEmpty();
get Value()
{
Node item := queue.pop();
Line 5,165 ⟶ 5,481:
</pre>
 
=={{header|FormulæFōrmulæ}}==
 
{{FormulaeEntry|page=https://formulae.org/?script=examples/Tree_traversal}}
Formulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation &mdash;i.e. XML, JSON&mdash; they are intended for storage and transfer purposes more than visualization and edition.
 
'''Solution'''
Programs in Formulæ are created/edited online in its [https://formulae.org website], However they run on execution servers. By default remote servers are used, but they are limited in memory and processing power, since they are intended for demonstration and casual use. A local server can be downloaded and installed, it has no limitations (it runs in your own computer). Because of that, example programs can be fully visualized and edited, but some of them will not run if they require a moderate or heavy computation/memory resources, and no local server is being used.
 
Notice that the action to do when visiting a node is provided as a lambda expression:
In '''[https://formulae.org/?example=Tree_traversal this]''' page you can see the program(s) related to this task and their results.
 
[[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 9,406 ⟶ 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 10,162 ⟶ 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,819 ⟶ 11,253:
{{trans|Kotlin}}
The object-oriented version.
<syntaxhighlight lang="ecmascriptwren">class Node {
construct new(v) {
_v = v
Alextretyak
1,480

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/339528...364300"