Rosetta Code

Tree traversal: Difference between revisions

Page Discussion

Tree traversal (view source)

Revision as of 02:45, 5 June 2024

7,065 bytes added ,  28 days ago
m
→‎{{header|Rust}}
(Add 8086 Assembly)
 
(14 intermediate revisions by 9 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 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 4,045 ⟶ 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,230 ⟶ 4,425:
 
=={{header|Elena}}==
ELENA 56.0x :
<syntaxhighlight lang="elena">import extensions;
import extensions'routines;
Line 4,243 ⟶ 4,438:
class Node
{
rprop int Value : rprop;
rprop Node Left : rprop;
rprop Node Right : rprop;
constructor new(int value)
Line 4,309 ⟶ 4,504:
LevelOrder = new Enumerable
{
Queue<Node> queue := class Queue<Node>.allocate(4).push:(self);
Enumerator enumerator() = new Enumerator
Line 4,315 ⟶ 4,510:
bool next() = queue.isNotEmpty();
get Value()
{
Node item := queue.pop();
Line 4,488 ⟶ 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 5,286 ⟶ 5,556:
</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,527 ⟶ 9,829:
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,980 ⟶ 10,324:
}
 
// LeftmostFrom left to rightmostright
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 popt = Some(self);
 
loopwhile {
// Stack parents and right children whileDescend left-descendingleftwards
loopwhile let Some(tree) = opt {
match pstack.right {push(tree);
Noneopt => {}tree.left.as_deref();
Some(box ref n) => stack.push(n),
}
stack.push(p);
match p.left {
None => break,
Some(box ref n) => p = n,
}
}
// Visit the nodes with no right child
p = stack.pop().unwrap();
while !stack.is_empty() && p.right.is_none() {
res.push(p);
p = stack.pop().unwrap();
}
// First node that can potentially have a right child:
res.push(p);
if stack.is_empty() {
break;
} else {
p = stack.pop().unwrap();
}
!stack.is_empty()
} {
let tree = stack.pop().unwrap();
res.push(tree);
opt = tree.right.as_deref();
}
res
Line 10,283 ⟶ 10,612:
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,940 ⟶ 11,313:
{{trans|Kotlin}}
The object-oriented version.
<syntaxhighlight lang="ecmascriptwren">class Node {
construct new(v) {
_v = v
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/339532...365000"