Tree traversal: Difference between revisions
Content added Content deleted
m (→Haskell: Reduced `treeLeaves` to a foldTree expression) |
(lang -> syntaxhighlight) |
||
Line 34: | Line 34: | ||
{{trans|Python: Class based}} |
{{trans|Python: Class based}} |
||
< |
<syntaxhighlight lang=11l>T Node |
||
Int data |
Int data |
||
Node? left |
Node? left |
||
Line 105: | Line 105: | ||
print(‘levelorder: ’, end' ‘’) |
print(‘levelorder: ’, end' ‘’) |
||
tree.levelorder(printwithspace) |
tree.levelorder(printwithspace) |
||
print()</ |
print()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 117: | Line 117: | ||
=={{header|AArch64 Assembly}}== |
=={{header|AArch64 Assembly}}== |
||
{{works with|as|Raspberry Pi 3B version Buster 64 bits}} |
{{works with|as|Raspberry Pi 3B version Buster 64 bits}} |
||
< |
<syntaxhighlight lang=AArch64 Assembly> |
||
/* ARM assembly AARCH64 Raspberry PI 3B */ |
/* ARM assembly AARCH64 Raspberry PI 3B */ |
||
/* program deftree64.s */ |
/* program deftree64.s */ |
||
Line 505: | Line 505: | ||
/* for this file see task include a file in language AArch64 assembly */ |
/* for this file see task include a file in language AArch64 assembly */ |
||
.include "../includeARM64.inc" |
.include "../includeARM64.inc" |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|ACL2}}== |
=={{header|ACL2}}== |
||
< |
<syntaxhighlight lang=lisp>(defun flatten-preorder (tree) |
||
(if (endp tree) |
(if (endp tree) |
||
nil |
nil |
||
Line 554: | Line 554: | ||
(defun flatten-level (tree) |
(defun flatten-level (tree) |
||
(let ((levels (flatten-level-r1 tree 0 nil))) |
(let ((levels (flatten-level-r1 tree 0 nil))) |
||
(flatten-level-r2 levels (len levels))))</ |
(flatten-level-r2 levels (len levels))))</syntaxhighlight> |
||
=={{header|Action!}}== |
=={{header|Action!}}== |
||
Line 560: | Line 560: | ||
The user must type in the monitor the following command after compilation and before running the program!<pre>SET EndProg=*</pre> |
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}} |
{{libheader|Action! Tool Kit}} |
||
< |
<syntaxhighlight lang=Action!>CARD EndProg ;required for ALLOCATE.ACT |
||
INCLUDE "D2:ALLOCATE.ACT" ;from the Action! Tool Kit. You must type 'SET EndProg=*' from the monitor after compiling, but before running this program! |
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: | Line 810: | ||
DestroyTree(t) |
DestroyTree(t) |
||
RETURN</ |
RETURN</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Tree_traversal.png Screenshot from Atari 8-bit computer] |
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Tree_traversal.png Screenshot from Atari 8-bit computer] |
||
Line 821: | Line 821: | ||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
< |
<syntaxhighlight lang=Ada>with Ada.Text_Io; use Ada.Text_Io; |
||
with Ada.Unchecked_Deallocation; |
with Ada.Unchecked_Deallocation; |
||
with Ada.Containers.Doubly_Linked_Lists; |
with Ada.Containers.Doubly_Linked_Lists; |
||
Line 928: | Line 928: | ||
New_Line; |
New_Line; |
||
Destroy_Tree(N); |
Destroy_Tree(N); |
||
end Tree_traversal;</ |
end Tree_traversal;</syntaxhighlight> |
||
=={{header|Agda}}== |
=={{header|Agda}}== |
||
< |
<syntaxhighlight lang=Agda>open import Data.List using (List; _?_; []; concat) |
||
open import Data.Nat using ( |
open import Data.Nat using (N; suc; zero) |
||
open import Level using (Level) |
open import Level using (Level) |
||
open import Relation.Binary.PropositionalEquality using ( |
open import Relation.Binary.PropositionalEquality using (_=_; refl) |
||
data Tree {a} (A : Set a) : Set a where |
data Tree {a} (A : Set a) : Set a where |
||
leaf : Tree A |
leaf : Tree A |
||
node : A |
node : A ? Tree A ? Tree A ? Tree A |
||
variable |
variable |
||
Line 944: | Line 944: | ||
A : Set a |
A : Set a |
||
preorder : Tree A |
preorder : Tree A ? List A |
||
preorder tr = go tr [] |
preorder tr = go tr [] |
||
where |
where |
||
go : Tree A |
go : Tree A ? List A ? List A |
||
go leaf ys = ys |
go leaf ys = ys |
||
go (node x ls rs) ys = x |
go (node x ls rs) ys = x ? go ls (go rs ys) |
||
inorder : Tree A |
inorder : Tree A ? List A |
||
inorder tr = go tr [] |
inorder tr = go tr [] |
||
where |
where |
||
go : Tree A |
go : Tree A ? List A ? List A |
||
go leaf ys = ys |
go leaf ys = ys |
||
go (node x ls rs) ys = go ls (x |
go (node x ls rs) ys = go ls (x ? go rs ys) |
||
postorder : Tree A |
postorder : Tree A ? List A |
||
postorder tr = go tr [] |
postorder tr = go tr [] |
||
where |
where |
||
go : Tree A |
go : Tree A ? List A ? List A |
||
go leaf ys = ys |
go leaf ys = ys |
||
go (node x ls rs) ys = go ls (go rs (x |
go (node x ls rs) ys = go ls (go rs (x ? ys)) |
||
level-order : Tree A |
level-order : Tree A ? List A |
||
level-order tr = concat (go tr []) |
level-order tr = concat (go tr []) |
||
where |
where |
||
go : Tree A |
go : Tree A ? List (List A) ? List (List A) |
||
go leaf qs = qs |
go leaf qs = qs |
||
go (node x ls rs) [] = (x |
go (node x ls rs) [] = (x ? []) ? go ls (go rs []) |
||
go (node x ls rs) (q |
go (node x ls rs) (q ? qs) = (x ? q ) ? go ls (go rs qs) |
||
example-tree : Tree |
example-tree : Tree N |
||
example-tree = |
example-tree = |
||
node 1 |
node 1 |
||
Line 995: | Line 995: | ||
leaf) |
leaf) |
||
_ : preorder example-tree |
_ : preorder example-tree = 1 ? 2 ? 4 ? 7 ? 5 ? 3 ? 6 ? 8 ? 9 ? [] |
||
_ = refl |
_ = refl |
||
_ : inorder example-tree |
_ : inorder example-tree = 7 ? 4 ? 2 ? 5 ? 1 ? 8 ? 6 ? 9 ? 3 ? [] |
||
_ = refl |
_ = refl |
||
_ : postorder example-tree |
_ : postorder example-tree = 7 ? 4 ? 5 ? 2 ? 8 ? 9 ? 6 ? 3 ? 1 ? [] |
||
_ = refl |
_ = refl |
||
_ : level-order example-tree |
_ : level-order example-tree = 1 ? 2 ? 3 ? 4 ? 5 ? 6 ? 7 ? 8 ? 9 ? [] |
||
_ = refl</ |
_ = refl</syntaxhighlight> |
||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
Line 1,017: | Line 1,017: | ||
{{works with|ELLA ALGOL 68|Any (with appropriate job cards)}} |
{{works with|ELLA ALGOL 68|Any (with appropriate job cards)}} |
||
< |
<syntaxhighlight lang=algol68>MODE VALUE = INT; |
||
PROC value repr = (VALUE value)STRING: whole(value, 0); |
PROC value repr = (VALUE value)STRING: whole(value, 0); |
||
Line 1,140: | Line 1,140: | ||
destroy tree(node) |
destroy tree(node) |
||
)</ |
)</syntaxhighlight> |
||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 1,152: | Line 1,152: | ||
Written in Dyalog APL with dfns. |
Written in Dyalog APL with dfns. |
||
< |
<syntaxhighlight lang=APL>preorder ? {l r?? ?? ? ? (?r)???(×?r)?(?l)???(×?l)?? ?? ?} |
||
inorder |
inorder ? {l r?? ?? ? ? (?r)???(×?r)?? ???(?l)???(×?l)??} |
||
postorder? {l r?? ?? ? ? ? ???(?r)???(×?r)?(?l)???(×?l)??} |
|||
postorder← {l r←⍺ ⍵⍵ ⍵ ⋄ ⍵ ⍺⍺⍨(⊃r)∇⍨⍣(×≢r)⊢(⊃l)∇⍨⍣(×≢l)⊢⍺} |
|||
lvlorder |
lvlorder ? {0=??:? ? (????/(??),??)??°(,/)?2??°??¨?}</syntaxhighlight> |
||
These accept four arguments (they are operators, a.k.a. higher-order functions): |
These accept four arguments (they are operators, a.k.a. higher-order functions): |
||
<pre>acc visit ___order children bintree</pre> |
<pre>acc visit ___order children bintree</pre> |
||
Line 1,174: | Line 1,174: | ||
and empty childL or childR mean and absence of the corresponding child node. |
and empty childL or childR mean and absence of the corresponding child node. |
||
< |
<syntaxhighlight lang=APL>tree?1(2(4(7??)?)(5??))(3(6(8??)(9??))?) |
||
visit?{?,(×??)???} |
|||
visit←{⍺,(×≢⍵)⍴⊃⍵} |
|||
children?{?¨@(×°?¨)1??}</syntaxhighlight> |
|||
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> |
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. |
My input into the interactive APL session is indented by 6 spaces. |
||
<pre> |
<pre> |
||
? visit preorder children tree |
|||
1 2 4 7 5 3 6 8 9 |
1 2 4 7 5 3 6 8 9 |
||
? visit inorder children tree |
|||
7 4 2 5 1 8 6 9 3 |
7 4 2 5 1 8 6 9 3 |
||
? visit postorder children tree |
|||
7 4 5 2 8 9 6 3 1 |
7 4 5 2 8 9 6 3 1 |
||
? visit lvlorder children ,?tree |
|||
1 2 3 4 5 6 7 8 9 |
1 2 3 4 5 6 7 8 9 |
||
</pre> |
</pre> |
||
Line 1,198: | Line 1,198: | ||
=={{header|AppleScript}}== |
=={{header|AppleScript}}== |
||
{{Trans|JavaScript}}(ES6) |
{{Trans|JavaScript}}(ES6) |
||
< |
<syntaxhighlight lang=AppleScript>on run |
||
-- Sample tree of integers |
-- Sample tree of integers |
||
set tree to node(1, ¬ |
set tree to node(1, ¬ |
||
Line 1,212: | Line 1,212: | ||
-- 'Visualize a Tree': |
-- 'Visualize a Tree': |
||
set strTree to unlines({¬ |
set strTree to unlines({¬ |
||
" |
" + 4 - 7", ¬ |
||
" |
" + 2 ¦", ¬ |
||
" |
" ¦ + 5", ¬ |
||
" 1 |
" 1 ¦", ¬ |
||
" |
" ¦ + 8", ¬ |
||
" |
" + 3 - 6 ¦", ¬ |
||
" |
" + 9"}) |
||
script tabulate |
script tabulate |
||
on | |
on |?|(s, xs) |
||
justifyRight(14, space, s & ": ") & unwords(xs) |
justifyRight(14, space, s & ": ") & unwords(xs) |
||
end | |
end |?| |
||
end script |
end script |
||
Line 1,249: | Line 1,249: | ||
-- inorder :: a -> [[a]] -> [a] |
-- inorder :: a -> [[a]] -> [a] |
||
on inorder(x, xs) |
on inorder(x, xs) |
||
if {} |
if {} ? xs then |
||
item 1 of xs & x & concat(rest of xs) |
item 1 of xs & x & concat(rest of xs) |
||
else |
else |
||
Line 1,272: | Line 1,272: | ||
on foldTree(f) |
on foldTree(f) |
||
script |
script |
||
on | |
on |?|(tree) |
||
script go |
script go |
||
property g : | |
property g : |?| of mReturn(f) |
||
on | |
on |?|(oNode) |
||
g(root of oNode, | |
g(root of oNode, |?|(nest of oNode) ¬ |
||
of map(go)) |
of map(go)) |
||
end | |
end |?| |
||
end script |
end script |
||
| |
|?|(tree) of go |
||
end | |
end |?| |
||
end script |
end script |
||
end foldTree |
end foldTree |
||
Line 1,306: | Line 1,306: | ||
tell mReturn(contents of f) |
tell mReturn(contents of f) |
||
repeat with x in xs |
repeat with x in xs |
||
set end of lst to | |
set end of lst to |?|(contents of x) |
||
end repeat |
end repeat |
||
end tell |
end tell |
||
Line 1,336: | Line 1,336: | ||
set lng to length of xs |
set lng to length of xs |
||
repeat with i from lng to 1 by -1 |
repeat with i from lng to 1 by -1 |
||
set v to | |
set v to |?|(item i of xs, v, i, xs) |
||
end repeat |
end repeat |
||
return v |
return v |
||
Line 1,369: | Line 1,369: | ||
-- values of each level of the tree. |
-- values of each level of the tree. |
||
script go |
script go |
||
on | |
on |?|(node, a) |
||
if {} |
if {} ? a then |
||
tell a to set {h, t} to {item 1, rest} |
tell a to set {h, t} to {item 1, rest} |
||
else |
else |
||
Line 1,377: | Line 1,377: | ||
{{root of node} & h} & foldr(go, t, nest of node) |
{{root of node} & h} & foldr(go, t, nest of node) |
||
end | |
end |?| |
||
end script |
end script |
||
| |
|?|(tree, {}) of go |
||
end levels |
end levels |
||
Line 1,390: | Line 1,390: | ||
else |
else |
||
script |
script |
||
property | |
property |?| : f |
||
end script |
end script |
||
end if |
end if |
||
Line 1,401: | Line 1,401: | ||
-- to each element of xs. |
-- to each element of xs. |
||
script |
script |
||
on | |
on |?|(xs) |
||
tell mReturn(f) |
tell mReturn(f) |
||
set lng to length of xs |
set lng to length of xs |
||
set lst to {} |
set lst to {} |
||
repeat with i from 1 to lng |
repeat with i from 1 to lng |
||
set end of lst to | |
set end of lst to |?|(item i of xs, i, xs) |
||
end repeat |
end repeat |
||
return lst |
return lst |
||
end tell |
end tell |
||
end | |
end |?| |
||
end script |
end script |
||
end map |
end map |
||
Line 1,473: | Line 1,473: | ||
set ys to {} |
set ys to {} |
||
repeat with i from 1 to n |
repeat with i from 1 to n |
||
set v to | |
set v to |?|() of xs |
||
if missing value is v then |
if missing value is v then |
||
return ys |
return ys |
||
Line 1,518: | Line 1,518: | ||
tell mReturn(f) |
tell mReturn(f) |
||
repeat with i from 1 to lng |
repeat with i from 1 to lng |
||
set end of lst to | |
set end of lst to |?|(item i of xs_, item i of ys_) |
||
end repeat |
end repeat |
||
return lst |
return lst |
||
end tell |
end tell |
||
end zipWith</ |
end zipWith</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> + 4 - 7 |
||
+ 2 ¦ |
|||
¦ + 5 |
|||
1 |
1 ¦ |
||
¦ + 8 |
|||
+ 3 - 6 ¦ |
|||
+ 9 |
|||
preorder: 1 2 4 7 5 3 6 8 9 |
preorder: 1 2 4 7 5 3 6 8 9 |
||
inorder: 7 4 2 5 1 8 6 9 3 |
inorder: 7 4 2 5 1 8 6 9 3 |
||
Line 1,538: | Line 1,538: | ||
=={{header|ARM Assembly}}== |
=={{header|ARM Assembly}}== |
||
{{works with|as|Raspberry Pi}} |
{{works with|as|Raspberry Pi}} |
||
< |
<syntaxhighlight lang=ARM Assembly> |
||
/* ARM assembly Raspberry PI */ |
/* ARM assembly Raspberry PI */ |
||
Line 1,975: | Line 1,975: | ||
iMagicNumber: .int 0xCCCCCCCD |
iMagicNumber: .int 0xCCCCCCCD |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{output}} |
{{output}} |
||
<pre> |
<pre> |
||
Line 2,022: | Line 2,022: | ||
=={{header|ATS}}== |
=={{header|ATS}}== |
||
< |
<syntaxhighlight lang=ATS>#include |
||
"share/atspre_staload.hats" |
"share/atspre_staload.hats" |
||
// |
// |
||
Line 2,119: | Line 2,119: | ||
println! ("postorder:\t", postorder(t0)); |
println! ("postorder:\t", postorder(t0)); |
||
println! ("level-order:\t", levelorder(t0)); |
println! ("level-order:\t", levelorder(t0)); |
||
end (* end of [main0] *)</ |
end (* end of [main0] *)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,129: | Line 2,129: | ||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
{{works with|AutoHotkey_L|45}} |
{{works with|AutoHotkey_L|45}} |
||
< |
<syntaxhighlight lang=AutoHotkey>AddNode(Tree,1,2,3,1) ; Build global Tree |
||
AddNode(Tree,2,4,5,2) |
AddNode(Tree,2,4,5,2) |
||
AddNode(Tree,3,6,0,3) |
AddNode(Tree,3,6,0,3) |
||
Line 2,181: | Line 2,181: | ||
t .= i%Lev%, Lev++ |
t .= i%Lev%, Lev++ |
||
Return t |
Return t |
||
}</ |
}</syntaxhighlight> |
||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
< |
<syntaxhighlight lang=awk> |
||
function preorder(tree, node, res, child) { |
function preorder(tree, node, res, child) { |
||
if (node == "") |
if (node == "") |
||
Line 2,274: | Line 2,274: | ||
delete result |
delete result |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Bracmat}}== |
=={{header|Bracmat}}== |
||
< |
<syntaxhighlight lang=bracmat>( |
||
( tree |
( tree |
||
= 1 |
= 1 |
||
Line 2,317: | Line 2,317: | ||
& out$("level-order:" levelorder$(!tree.)) |
& out$("level-order:" levelorder$(!tree.)) |
||
& |
& |
||
)</ |
)</syntaxhighlight> |
||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<syntaxhighlight lang=c>#include <stdlib.h> |
||
#include <stdio.h> |
#include <stdio.h> |
||
Line 2,465: | Line 2,465: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|C sharp}}== |
=={{header|C sharp}}== |
||
< |
<syntaxhighlight lang=csharp>using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
using System.Linq; |
using System.Linq; |
||
Line 2,539: | Line 2,539: | ||
Console.WriteLine("{0}:\t{1}", traversal.Method.Name, string.Join(" ", traversal())); |
Console.WriteLine("{0}:\t{1}", traversal.Method.Name, string.Join(" ", traversal())); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|C++}}== |
=={{header|C++}}== |
||
Line 2,546: | Line 2,546: | ||
{{libheader|Boost|1.39.0}} |
{{libheader|Boost|1.39.0}} |
||
< |
<syntaxhighlight lang=cpp>#include <boost/scoped_ptr.hpp> |
||
#include <iostream> |
#include <iostream> |
||
#include <queue> |
#include <queue> |
||
Line 2,639: | Line 2,639: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
===Array version=== |
===Array version=== |
||
< |
<syntaxhighlight lang=cpp>#include <iostream> |
||
using namespace std; |
using namespace std; |
||
Line 2,710: | Line 2,710: | ||
level_order(t); |
level_order(t); |
||
cout << endl; |
cout << endl; |
||
}</ |
}</syntaxhighlight> |
||
===Modern C++=== |
===Modern C++=== |
||
{{works with|C++14}} |
{{works with|C++14}} |
||
< |
<syntaxhighlight lang=cpp>#include <iostream> |
||
#include <memory> |
#include <memory> |
||
#include <queue> |
#include <queue> |
||
Line 2,808: | Line 2,808: | ||
n.level_order(print); |
n.level_order(print); |
||
std::cout << '\n'; |
std::cout << '\n'; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,819: | Line 2,819: | ||
=={{header|Ceylon}}== |
=={{header|Ceylon}}== |
||
< |
<syntaxhighlight lang=ceylon>import ceylon.collection { |
||
ArrayList |
ArrayList |
||
} |
} |
||
Line 2,915: | Line 2,915: | ||
levelOrder(tree); |
levelOrder(tree); |
||
print(""); |
print(""); |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
< |
<syntaxhighlight lang=clojure>(defn walk [node f order] |
||
(when node |
(when node |
||
(doseq [o order] |
(doseq [o order] |
||
Line 2,961: | Line 2,961: | ||
(print (format "%-12s" (str f ":"))) |
(print (format "%-12s" (str f ":"))) |
||
((resolve f) tree pr-node) |
((resolve f) tree pr-node) |
||
(println)))</ |
(println)))</syntaxhighlight> |
||
=={{header|CLU}}== |
=={{header|CLU}}== |
||
< |
<syntaxhighlight lang=clu>bintree = cluster [T: type] is leaf, node, |
||
pre_order, post_order, in_order, level_order |
pre_order, post_order, in_order, level_order |
||
branch = struct[left, right: bintree[T], val: T] |
branch = struct[left, right: bintree[T], val: T] |
||
Line 3,057: | Line 3,057: | ||
stream$puts(po, " " || int$unparse(i)) |
stream$puts(po, " " || int$unparse(i)) |
||
end |
end |
||
end start_up</ |
end start_up</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>preorder: 1 2 4 7 5 3 6 8 9 |
<pre>preorder: 1 2 4 7 5 3 6 8 9 |
||
Line 3,065: | Line 3,065: | ||
=={{header|CoffeeScript}}== |
=={{header|CoffeeScript}}== |
||
< |
<syntaxhighlight lang=coffeescript> |
||
# In this example, we don't encapsulate binary trees as objects; instead, we have a |
# 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 |
# convention on how to store them as arrays, and we namespace the functions that |
||
Line 3,112: | Line 3,112: | ||
test_walk "postorder" |
test_walk "postorder" |
||
test_walk "levelorder" |
test_walk "levelorder" |
||
</syntaxhighlight> |
|||
</lang> |
|||
output |
output |
||
<syntaxhighlight> |
|||
<lang> |
|||
> coffee tree_traversal.coffee |
> coffee tree_traversal.coffee |
||
preorder 1 2 4 7 5 3 6 8 9 |
preorder 1 2 4 7 5 3 6 8 9 |
||
Line 3,120: | Line 3,120: | ||
postorder 7 4 5 2 8 9 6 3 1 |
postorder 7 4 5 2 8 9 6 3 1 |
||
levelorder 1 2 3 4 5 6 7 8 9 |
levelorder 1 2 3 4 5 6 7 8 9 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
< |
<syntaxhighlight lang=lisp>(defun preorder (node f) |
||
(when node |
(when node |
||
(funcall f (first node)) |
(funcall f (first node)) |
||
Line 3,161: | Line 3,161: | ||
(funcall traversal-function *tree* (lambda (value) (format t " ~A" value)))) |
(funcall traversal-function *tree* (lambda (value) (format t " ~A" value)))) |
||
(map nil #'show '(preorder inorder postorder level-order))</ |
(map nil #'show '(preorder inorder postorder level-order))</syntaxhighlight> |
||
Output: |
Output: |
||
Line 3,172: | Line 3,172: | ||
=={{header|Coq}}== |
=={{header|Coq}}== |
||
< |
<syntaxhighlight lang=coq>Require Import Utf8. |
||
Require Import List. |
Require Import List. |
||
Line 3,181: | Line 3,181: | ||
Fixpoint height (t: tree) : nat := |
Fixpoint height (t: tree) : nat := |
||
1 + fold_left ( |
1 + fold_left (? n t, max n (height t)) (children t) 0. |
||
Example leaf n : tree := {| value := n ; children := nil |}. |
Example leaf n : tree := {| value := n ; children := nil |}. |
||
Line 3,199: | Line 3,199: | ||
match c with |
match c with |
||
| nil => n :: nil |
| nil => n :: nil |
||
| |
| l :: r => inorder l ++ n :: flat_map inorder r |
||
end. |
end. |
||
Line 3,212: | Line 3,212: | ||
| O => nil |
| O => nil |
||
| S fuel' => |
| S fuel' => |
||
let '(p, f) := fold_right ( |
let '(p, f) := fold_right (? t r, let '(x, f) := r in (value t :: x, children t ++ f) ) (nil, nil) f in |
||
p ++ levelorder_forest fuel' f |
p ++ levelorder_forest fuel' f |
||
end. |
end. |
||
Line 3,223: | Line 3,223: | ||
Compute postorder t9. |
Compute postorder t9. |
||
Compute levelorder t9. |
Compute levelorder t9. |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Crystal}}== |
=={{header|Crystal}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang=crystal> |
||
class Node(T) |
class Node(T) |
||
property left : Nil | Node(T) |
property left : Nil | Node(T) |
||
Line 3,309: | Line 3,309: | ||
puts |
puts |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 3,320: | Line 3,320: | ||
=={{header|D}}== |
=={{header|D}}== |
||
This code is long because it's very generic. |
This code is long because it's very generic. |
||
< |
<syntaxhighlight lang=d>import std.stdio, std.traits; |
||
const final class Node(T) { |
const final class Node(T) { |
||
Line 3,396: | Line 3,396: | ||
tree.levelOrder; |
tree.levelOrder; |
||
writeln; |
writeln; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> preOrder: 1 2 4 7 5 3 6 8 9 |
<pre> preOrder: 1 2 4 7 5 3 6 8 9 |
||
Line 3,406: | Line 3,406: | ||
{{trans|Haskell}} |
{{trans|Haskell}} |
||
Generic as the first version, but not lazy as the Haskell version. |
Generic as the first version, but not lazy as the Haskell version. |
||
< |
<syntaxhighlight lang=d>const struct Node(T) { |
||
T v; |
T v; |
||
Node* l, r; |
Node* l, r; |
||
Line 3,449: | Line 3,449: | ||
writeln(postOrder(tree)); |
writeln(postOrder(tree)); |
||
writeln(levelOrder(tree)); |
writeln(levelOrder(tree)); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[1, 2, 4, 7, 5, 3, 6, 8, 9] |
<pre>[1, 2, 4, 7, 5, 3, 6, 8, 9] |
||
Line 3,458: | Line 3,458: | ||
===Alternative Lazy Version=== |
===Alternative Lazy Version=== |
||
This version is not complete, it lacks the level order visit. |
This version is not complete, it lacks the level order visit. |
||
< |
<syntaxhighlight lang=d>import std.stdio, std.algorithm, std.range, std.string; |
||
const struct Tree(T) { |
const struct Tree(T) { |
||
Line 3,522: | Line 3,522: | ||
tree.inOrder.map!(t => t.value).writeln; |
tree.inOrder.map!(t => t.value).writeln; |
||
tree.postOrder.map!(t => t.value).writeln; |
tree.postOrder.map!(t => t.value).writeln; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[1, 2, 4, 7, 5, 3, 6, 8, 9] |
<pre>[1, 2, 4, 7, 5, 3, 6, 8, 9] |
||
Line 3,530: | Line 3,530: | ||
=={{header|E}}== |
=={{header|E}}== |
||
< |
<syntaxhighlight lang=e>def btree := [1, [2, [4, [7, null, null], |
||
null], |
null], |
||
[5, null, null]], |
[5, null, null]], |
||
Line 3,576: | Line 3,576: | ||
print("level-order:") |
print("level-order:") |
||
levelOrder(btree, fn v { print(" ", v) }) |
levelOrder(btree, fn v { print(" ", v) }) |
||
println()</ |
println()</syntaxhighlight> |
||
=={{header|Eiffel}}== |
=={{header|Eiffel}}== |
||
Line 3,582: | Line 3,582: | ||
Void-Safety has been disabled for simplicity of the code. |
Void-Safety has been disabled for simplicity of the code. |
||
< |
<syntaxhighlight lang=eiffel >note |
||
description : "Application for tree traversal demonstration" |
description : "Application for tree traversal demonstration" |
||
output : "[ |
output : "[ |
||
Line 3,632: | Line 3,632: | ||
end |
end |
||
end -- class APPLICATION</ |
end -- class APPLICATION</syntaxhighlight> |
||
< |
<syntaxhighlight lang=eiffel >note |
||
description : "A simple node for a binary tree" |
description : "A simple node for a binary tree" |
||
libraries : "Relies on LINKED_LIST from EiffelBase" |
libraries : "Relies on LINKED_LIST from EiffelBase" |
||
Line 3,759: | Line 3,759: | ||
end |
end |
||
-- class NODE</ |
-- class NODE</syntaxhighlight> |
||
=={{header|Elena}}== |
=={{header|Elena}}== |
||
ELENA 5.0 : |
ELENA 5.0 : |
||
< |
<syntaxhighlight lang=elena>import extensions; |
||
import extensions'routines; |
import extensions'routines; |
||
import system'collections; |
import system'collections; |
||
Line 3,883: | Line 3,883: | ||
console.printLine("Postorder :", tree.Postorder); |
console.printLine("Postorder :", tree.Postorder); |
||
console.printLine("LevelOrder:", tree.LevelOrder) |
console.printLine("LevelOrder:", tree.LevelOrder) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,894: | Line 3,894: | ||
=={{header|Elisa}}== |
=={{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]. |
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); |
component BinaryTreeTraversals (Tree, Element); |
||
type Tree; |
type Tree; |
||
Line 3,931: | Line 3,931: | ||
]; |
]; |
||
end component BinaryTreeTraversals; |
end component BinaryTreeTraversals; |
||
</syntaxhighlight> |
|||
</lang> |
|||
Tests |
Tests |
||
< |
<syntaxhighlight lang=Elisa> |
||
use BinaryTreeTraversals (Tree, integer); |
use BinaryTreeTraversals (Tree, integer); |
||
Line 3,953: | Line 3,953: | ||
{Item(Level_order(BT))}? |
{Item(Level_order(BT))}? |
||
{ 1, 2, 3, 4, 5, 6, 7, 8, 9} |
{ 1, 2, 3, 4, 5, 6, 7, 8, 9} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
{{trans|Erlang}} |
{{trans|Erlang}} |
||
< |
<syntaxhighlight lang=elixir>defmodule Tree_Traversal do |
||
defp tnode, do: {} |
defp tnode, do: {} |
||
defp tnode(v), do: {:node, v, {}, {}} |
defp tnode(v), do: {:node, v, {}, {}} |
||
Line 4,012: | Line 4,012: | ||
end |
end |
||
Tree_Traversal.main</ |
Tree_Traversal.main</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 4,023: | Line 4,023: | ||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
< |
<syntaxhighlight lang=erlang>-module(tree_traversal). |
||
-export([main/0]). |
-export([main/0]). |
||
-export([preorder/2, inorder/2, postorder/2, levelorder/2]). |
-export([preorder/2, inorder/2, postorder/2, levelorder/2]). |
||
Line 4,064: | Line 4,064: | ||
inorder(F, Tree), ?NEWLINE, |
inorder(F, Tree), ?NEWLINE, |
||
postorder(F, Tree), ?NEWLINE, |
postorder(F, Tree), ?NEWLINE, |
||
levelorder(F, Tree), ?NEWLINE.</ |
levelorder(F, Tree), ?NEWLINE.</syntaxhighlight> |
||
Output: |
Output: |
||
Line 4,074: | Line 4,074: | ||
=={{header|Euphoria}}== |
=={{header|Euphoria}}== |
||
< |
<syntaxhighlight lang=euphoria>constant VALUE = 1, LEFT = 2, RIGHT = 3 |
||
constant tree = {1, |
constant tree = {1, |
||
Line 4,140: | Line 4,140: | ||
puts(1,"level-order: ") |
puts(1,"level-order: ") |
||
level_order(tree) |
level_order(tree) |
||
puts(1,'\n')</ |
puts(1,'\n')</syntaxhighlight> |
||
Output: |
Output: |
||
Line 4,149: | Line 4,149: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
< |
<syntaxhighlight lang=fsharp>open System |
||
open System.IO |
open System.IO |
||
Line 4,223: | Line 4,223: | ||
printf "\nlevel-order: " |
printf "\nlevel-order: " |
||
levelorder tree |> Seq.iter show |
levelorder tree |> Seq.iter show |
||
0</ |
0</syntaxhighlight> |
||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang=factor>USING: accessors combinators deques dlists fry io kernel |
||
math.parser ; |
math.parser ; |
||
IN: rosetta.tree-traversal |
IN: rosetta.tree-traversal |
||
Line 4,297: | Line 4,297: | ||
[ "levelorder: " write levelorder nl ] |
[ "levelorder: " write levelorder nl ] |
||
[ "levelorder2: " write levelorder2 nl ] |
[ "levelorder2: " write levelorder2 nl ] |
||
} 2cleave ;</ |
} 2cleave ;</syntaxhighlight> |
||
=={{header|Fantom}}== |
=={{header|Fantom}}== |
||
< |
<syntaxhighlight lang=fantom> |
||
class Tree |
class Tree |
||
{ |
{ |
||
Line 4,370: | Line 4,370: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
Line 4,381: | Line 4,381: | ||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
< |
<syntaxhighlight lang=forth>\ binary tree (dictionary) |
||
: node ( l r data -- node ) here >r , , , r> ; |
: node ( l r data -- node ) here >r , , , r> ; |
||
: leaf ( data -- node ) 0 0 rot node ; |
: leaf ( data -- node ) 0 0 rot node ; |
||
Line 4,436: | Line 4,436: | ||
cr ' . tree postorder \ 7 4 5 2 8 9 6 3 1 |
cr ' . tree postorder \ 7 4 5 2 8 9 6 3 1 |
||
cr tree max-depth . \ 4 |
cr tree max-depth . \ 4 |
||
cr ' . tree levelorder \ 1 2 3 4 5 6 7 8 9</ |
cr ' . tree levelorder \ 1 2 3 4 5 6 7 8 9</syntaxhighlight> |
||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
Line 4,446: | Line 4,446: | ||
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. |
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 < |
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 <syntaxhighlight lang=Fortran> |
||
IF (STYLE.EQ."PRE") CALL OUT(HAS) |
IF (STYLE.EQ."PRE") CALL OUT(HAS) |
||
IF (LINKL(HAS).GT.0) CALL TARZAN(LINKL(HAS),STYLE) |
IF (LINKL(HAS).GT.0) CALL TARZAN(LINKL(HAS),STYLE) |
||
IF (STYLE.EQ."IN") CALL OUT(HAS) |
IF (STYLE.EQ."IN") CALL OUT(HAS) |
||
IF (LINKR(HAS).GT.0) CALL TARZAN(LINKR(HAS),STYLE) |
IF (LINKR(HAS).GT.0) CALL TARZAN(LINKR(HAS),STYLE) |
||
IF (STYLE.EQ."POST") CALL OUT(HAS)</ |
IF (STYLE.EQ."POST") CALL OUT(HAS)</syntaxhighlight> |
||
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. |
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: | Line 4,458: | ||
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. |
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 < |
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 <syntaxhighlight lang=Fortran> |
||
DO GASP = 1,MAXLEVEL |
DO GASP = 1,MAXLEVEL |
||
CALL TARZAN(1,HOW) |
CALL TARZAN(1,HOW) |
||
END DO</ |
END DO</syntaxhighlight> |
||
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. |
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=== |
===Source=== |
||
< |
<syntaxhighlight lang=Fortran> |
||
MODULE ARAUCARIA !Cunning crosswords, also. |
MODULE ARAUCARIA !Cunning crosswords, also. |
||
INTEGER ENUFF !To suit the set example. |
INTEGER ENUFF !To suit the set example. |
||
Line 4,668: | Line 4,668: | ||
CALL JANE("LEVEL") !Alternatively... |
CALL JANE("LEVEL") !Alternatively... |
||
END !So much for that. |
END !So much for that. |
||
</syntaxhighlight> |
|||
</lang> |
|||
===Output=== |
===Output=== |
||
Alternately GORILLA-style, and JANE-style: |
Alternately GORILLA-style, and JANE-style: |
||
Line 4,687: | Line 4,687: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang=freebasic> |
||
#define NULL 0 |
#define NULL 0 |
||
Line 4,760: | Line 4,760: | ||
Wend |
Wend |
||
End Sub |
End Sub |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,772: | Line 4,772: | ||
=={{header|FunL}}== |
=={{header|FunL}}== |
||
{{trans|Haskell}} |
{{trans|Haskell}} |
||
< |
<syntaxhighlight lang=funl>data Tree = Empty | Node( value, left, right ) |
||
def |
def |
||
Line 4,807: | Line 4,807: | ||
println( inorder(tree) ) |
println( inorder(tree) ) |
||
println( postorder(tree) ) |
println( postorder(tree) ) |
||
println( levelorder(tree) )</ |
println( levelorder(tree) )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 4,818: | Line 4,818: | ||
</pre> |
</pre> |
||
=={{header| |
=={{header|Formulæ}}== |
||
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 —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition. |
|||
Programs in |
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. |
||
In '''[https://formulae.org/?example=Tree_traversal this]''' page you can see the program(s) related to this task and their results. |
In '''[https://formulae.org/?example=Tree_traversal this]''' page you can see the program(s) related to this task and their results. |
||
Line 4,828: | Line 4,828: | ||
=={{header|GFA Basic}}== |
=={{header|GFA Basic}}== |
||
<syntaxhighlight> |
|||
<lang> |
|||
maxnodes%=100 ! set a limit to size of tree |
maxnodes%=100 ! set a limit to size of tree |
||
content%=0 ! index of content field |
content%=0 ! index of content field |
||
Line 4,945: | Line 4,945: | ||
WEND |
WEND |
||
RETURN |
RETURN |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
Line 4,951: | Line 4,951: | ||
{{trans|C}} |
{{trans|C}} |
||
This is like many examples on this page. |
This is like many examples on this page. |
||
< |
<syntaxhighlight lang=go>package main |
||
import "fmt" |
import "fmt" |
||
Line 5,036: | Line 5,036: | ||
func visitor(value int) { |
func visitor(value int) { |
||
fmt.Print(value, " ") |
fmt.Print(value, " ") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 5,046: | Line 5,046: | ||
===Flat slice=== |
===Flat slice=== |
||
Alternative representation. Like Wikipedia [http://en.wikipedia.org/wiki/Binary_tree#Arrays Binary tree#Arrays] |
Alternative representation. Like Wikipedia [http://en.wikipedia.org/wiki/Binary_tree#Arrays Binary tree#Arrays] |
||
< |
<syntaxhighlight lang=go>package main |
||
import "fmt" |
import "fmt" |
||
Line 5,116: | Line 5,116: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
Uses Groovy '''Node''' and '''NodeBuilder''' classes |
Uses Groovy '''Node''' and '''NodeBuilder''' classes |
||
< |
<syntaxhighlight lang=groovy>def preorder; |
||
preorder = { Node node -> |
preorder = { Node node -> |
||
([node] + node.children().collect { preorder(it) }).flatten() |
([node] + node.children().collect { preorder(it) }).flatten() |
||
Line 5,154: | Line 5,154: | ||
node |
node |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Verify that '''BinaryNodeBuilder''' will not allow a node to have more than 2 children |
Verify that '''BinaryNodeBuilder''' will not allow a node to have more than 2 children |
||
< |
<syntaxhighlight lang=groovy>try { |
||
new BinaryNodeBuilder().'1' { |
new BinaryNodeBuilder().'1' { |
||
a {} |
a {} |
||
Line 5,166: | Line 5,166: | ||
} catch (org.codehaus.groovy.transform.powerassert.PowerAssertionError e) { |
} catch (org.codehaus.groovy.transform.powerassert.PowerAssertionError e) { |
||
println 'limited to binary tree\r\n' |
println 'limited to binary tree\r\n' |
||
}</ |
}</syntaxhighlight> |
||
Test case #1 (from the task definition) |
Test case #1 (from the task definition) |
||
< |
<syntaxhighlight lang=groovy>// 1 |
||
// / \ |
// / \ |
||
// 2 3 |
// 2 3 |
||
Line 5,185: | Line 5,185: | ||
'6' { '8' {}; '9' {} } |
'6' { '8' {}; '9' {} } |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Test case #2 (tests single right child) |
Test case #2 (tests single right child) |
||
< |
<syntaxhighlight lang=groovy>// 1 |
||
// / \ |
// / \ |
||
// 2 3 |
// 2 3 |
||
Line 5,204: | Line 5,204: | ||
'6' { '8' {}; '9' {} } |
'6' { '8' {}; '9' {} } |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Run tests: |
Run tests: |
||
< |
<syntaxhighlight lang=groovy>def test = { tree -> |
||
println "preorder: ${preorder(tree).collect{it.name()}}" |
println "preorder: ${preorder(tree).collect{it.name()}}" |
||
println "preorder: ${tree.depthFirst().collect{it.name()}}" |
println "preorder: ${tree.depthFirst().collect{it.name()}}" |
||
Line 5,221: | Line 5,221: | ||
} |
} |
||
test(tree1) |
test(tree1) |
||
test(tree2)</ |
test(tree2)</syntaxhighlight> |
||
Output: |
Output: |
||
Line 5,242: | Line 5,242: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
===Left Right nodes=== |
===Left Right nodes=== |
||
< |
<syntaxhighlight lang=haskell>---------------------- TREE TRAVERSAL -------------------- |
||
data Tree a |
data Tree a |
||
Line 5,311: | Line 5,311: | ||
([preorder, inorder, postorder, levelorder] <*> [tree]) |
([preorder, inorder, postorder, levelorder] <*> [tree]) |
||
where |
where |
||
justifyLeft n c s = take n (s <> replicate n c)</ |
justifyLeft n c s = take n (s <> replicate n c)</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> 1 |
<pre> 1 |
||
Line 5,452: | Line 5,452: | ||
=={{header|Icon}} and {{header|Unicon}}== |
=={{header|Icon}} and {{header|Unicon}}== |
||
< |
<syntaxhighlight lang=Icon>procedure main() |
||
bTree := [1, [2, [4, [7]], [5]], [3, [6, [8], [9]]]] |
bTree := [1, [2, [4, [7]], [5]], [3, [6, [8], [9]]]] |
||
showTree(bTree, preorder|inorder|postorder|levelorder) |
showTree(bTree, preorder|inorder|postorder|levelorder) |
||
Line 5,483: | Line 5,483: | ||
} |
} |
||
} |
} |
||
end</ |
end</syntaxhighlight> |
||
Output: |
Output: |
||
Line 5,495: | Line 5,495: | ||
=={{header|Isabelle}}== |
=={{header|Isabelle}}== |
||
< |
<syntaxhighlight lang=Isabelle>theory Tree |
||
imports Main |
imports Main |
||
begin |
begin |
||
Line 5,502: | Line 5,502: | ||
definition example :: "int tree" where |
definition example :: "int tree" where |
||
"example |
"example = |
||
Node |
Node |
||
(Node |
(Node |
||
Line 5,524: | Line 5,524: | ||
)" |
)" |
||
fun preorder :: "'a tree |
fun preorder :: "'a tree ? 'a list" where |
||
"preorder Leaf = []" |
"preorder Leaf = []" |
||
| "preorder (Node l a r) = a # preorder l @ preorder r" |
| "preorder (Node l a r) = a # preorder l @ preorder r" |
||
Line 5,530: | Line 5,530: | ||
lemma "preorder example = [1, 2, 4, 7, 5, 3, 6, 8, 9]" by code_simp |
lemma "preorder example = [1, 2, 4, 7, 5, 3, 6, 8, 9]" by code_simp |
||
fun inorder :: "'a tree |
fun inorder :: "'a tree ? 'a list" where |
||
"inorder Leaf = []" |
"inorder Leaf = []" |
||
| "inorder (Node l a r) = inorder l @ [a] @ inorder r" |
| "inorder (Node l a r) = inorder l @ [a] @ inorder r" |
||
Line 5,536: | Line 5,536: | ||
lemma "inorder example = [7, 4, 2, 5, 1, 8, 6, 9, 3]" by code_simp |
lemma "inorder example = [7, 4, 2, 5, 1, 8, 6, 9, 3]" by code_simp |
||
fun postorder :: "'a tree |
fun postorder :: "'a tree ? 'a list" where |
||
"postorder Leaf = []" |
"postorder Leaf = []" |
||
| "postorder (Node l a r) = postorder l @ postorder r @ [a]" |
| "postorder (Node l a r) = postorder l @ postorder r @ [a]" |
||
Line 5,556: | Line 5,556: | ||
so we provide some help by defining what the size of a tree is. |
so we provide some help by defining what the size of a tree is. |
||
› |
› |
||
fun tree_size :: "'a tree |
fun tree_size :: "'a tree ? nat" where |
||
"tree_size Leaf = 1" |
"tree_size Leaf = 1" |
||
| "tree_size (Node l _ r) = 1 + tree_size l + tree_size r" |
| "tree_size (Node l _ r) = 1 + tree_size l + tree_size r" |
||
function (sequential) bfs :: "'a tree list |
function (sequential) bfs :: "'a tree list ? 'a list" where |
||
"bfs [] = []" |
"bfs [] = []" |
||
| "bfs (Leaf#q) = bfs q" |
| "bfs (Leaf#q) = bfs q" |
||
Line 5,566: | Line 5,566: | ||
by pat_completeness auto |
by pat_completeness auto |
||
termination bfs |
termination bfs |
||
by(relation "measure ( |
by(relation "measure (?qs. sum_list (map tree_size qs))") simp+ |
||
fun levelorder :: "'a tree |
fun levelorder :: "'a tree ? 'a list" where |
||
"levelorder t = bfs [t]" |
"levelorder t = bfs [t]" |
||
lemma "levelorder example = [1, 2, 3, 4, 5, 6, 7, 8, 9]" by code_simp |
lemma "levelorder example = [1, 2, 3, 4, 5, 6, 7, 8, 9]" by code_simp |
||
end</ |
end</syntaxhighlight> |
||
=={{header|J}}== |
=={{header|J}}== |
||
< |
<syntaxhighlight lang=J>preorder=: ]S:0 |
||
postorder=: ([:; postorder&.>@}.) , >@{. |
postorder=: ([:; postorder&.>@}.) , >@{. |
||
levelorder=: ;@({::L:1 _~ [: (/: #@>) <S:1@{::) |
levelorder=: ;@({::L:1 _~ [: (/: #@>) <S:1@{::) |
||
inorder=: ([:; inorder&.>@(''"_`(1&{)@.(1<#))) , >@{. , [:; inorder&.>@}.@}.</ |
inorder=: ([:; inorder&.>@(''"_`(1&{)@.(1<#))) , >@{. , [:; inorder&.>@}.@}.</syntaxhighlight> |
||
Required example: |
Required example: |
||
< |
<syntaxhighlight lang=J>N2=: conjunction def '(<m),(<n),<y' |
||
N1=: adverb def '(<m),<y' |
N1=: adverb def '(<m),<y' |
||
L=: adverb def '<m' |
L=: adverb def '<m' |
||
tree=: 1 N2 (2 N2 (4 N1 (7 L)) 5 L) 3 N1 6 N2 (8 L) 9 L</ |
tree=: 1 N2 (2 N2 (4 N1 (7 L)) 5 L) 3 N1 6 N2 (8 L) 9 L</syntaxhighlight> |
||
This tree is organized in a pre-order fashion |
This tree is organized in a pre-order fashion |
||
< |
<syntaxhighlight lang=J> preorder tree |
||
1 2 4 7 5 3 6 8 9</ |
1 2 4 7 5 3 6 8 9</syntaxhighlight> |
||
post-order is not that much different from pre-order, except that the children must extracted before the parent. |
post-order is not that much different from pre-order, except that the children must extracted before the parent. |
||
< |
<syntaxhighlight lang=J> postorder tree |
||
7 4 5 2 8 9 6 3 1</ |
7 4 5 2 8 9 6 3 1</syntaxhighlight> |
||
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 |
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 |
||
< |
<syntaxhighlight lang=J> inorder tree |
||
7 4 2 5 1 8 6 9 3</ |
7 4 2 5 1 8 6 9 3</syntaxhighlight> |
||
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. |
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. |
||
< |
<syntaxhighlight lang=J> levelorder tree |
||
1 2 3 4 5 6 7 8 9</ |
1 2 3 4 5 6 7 8 9</syntaxhighlight> |
||
For J novices, here's the tree instance with a few redundant parenthesis: |
For J novices, here's the tree instance with a few redundant parenthesis: |
||
< |
<syntaxhighlight lang=J> tree=: 1 N2 (2 N2 (4 N1 (7 L)) (5 L)) (3 N1 (6 N2 (8 L) (9 L)))</syntaxhighlight> |
||
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.) |
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,621: | Line 5,621: | ||
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: |
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: |
||
< |
<syntaxhighlight lang=J>example=:1 8 3 4 7 5 9 6 2,: 0 7 0 8 3 8 7 2 0</syntaxhighlight> |
||
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. |
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,627: | Line 5,627: | ||
Next, let's define a few utilities: |
Next, let's define a few utilities: |
||
< |
<syntaxhighlight lang=J>depth=: +/@((~: , (~: i.@#@{.)~) {:@,)@({~^:a:) |
||
reorder=:4 :0 |
reorder=:4 :0 |
||
Line 5,639: | Line 5,639: | ||
parent=:3 :'parent[''data parent''=. y' |
parent=:3 :'parent[''data parent''=. y' |
||
childinds=: [: <:@(2&{.@-.&> #\) (</. #\)`(]~.)`(a:"0)}~</ |
childinds=: [: <:@(2&{.@-.&> #\) (</. #\)`(]~.)`(a:"0)}~</syntaxhighlight> |
||
Here, <code>data</code> extracts the list of data items from the tree and <code>parent</code> extracts the structure from the tree. |
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,651: | Line 5,651: | ||
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): |
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): |
||
< |
<syntaxhighlight lang=J>dataorder=: /:@data reorder ] |
||
levelorder=: /:@depth@parent reorder ] |
levelorder=: /:@depth@parent reorder ] |
||
Line 5,703: | Line 5,703: | ||
todo=. todo,|.ch end. end. |
todo=. todo,|.ch end. end. |
||
r |
r |
||
)</ |
)</syntaxhighlight> |
||
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. |
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,709: | Line 5,709: | ||
Example use: |
Example use: |
||
< |
<syntaxhighlight lang=J> levelorder dataorder example |
||
1 2 3 4 5 6 7 8 9 |
1 2 3 4 5 6 7 8 9 |
||
0 0 0 1 1 2 3 5 5 |
0 0 0 1 1 2 3 5 5 |
||
Line 5,720: | Line 5,720: | ||
postorder dataorder example |
postorder dataorder example |
||
7 4 5 2 8 9 6 3 1 |
7 4 5 2 8 9 6 3 1 |
||
1 3 3 8 6 6 7 8 8</ |
1 3 3 8 6 6 7 8 8</syntaxhighlight> |
||
(Once again, all we really need for this task is the first row of those results - the part that represents data.) |
(Once again, all we really need for this task is the first row of those results - the part that represents data.) |
||
Line 5,732: | Line 5,732: | ||
{{works with|Java|1.5+}} |
{{works with|Java|1.5+}} |
||
< |
<syntaxhighlight lang=java5>import java.util.*; |
||
public class TreeTraversal { |
public class TreeTraversal { |
||
Line 5,818: | Line 5,818: | ||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>1 2 4 7 5 3 6 8 9 |
<pre>1 2 4 7 5 3 6 8 9 |
||
Line 5,833: | Line 5,833: | ||
{{works with|Java|1.8+}} |
{{works with|Java|1.8+}} |
||
< |
<syntaxhighlight lang=java5>import java.util.function.Consumer; |
||
import java.util.Queue; |
import java.util.Queue; |
||
import java.util.LinkedList; |
import java.util.LinkedList; |
||
Line 5,958: | Line 5,958: | ||
System.out.println(); |
System.out.println(); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Output: |
Output: |
||
Line 5,970: | Line 5,970: | ||
====Iteration==== |
====Iteration==== |
||
inspired by [[#Ruby|Ruby]] |
inspired by [[#Ruby|Ruby]] |
||
< |
<syntaxhighlight lang=javascript>function BinaryTree(value, left, right) { |
||
this.value = value; |
this.value = value; |
||
this.left = left; |
this.left = left; |
||
Line 6,009: | Line 6,009: | ||
print("*** inorder ***"); tree.inorder(print); |
print("*** inorder ***"); tree.inorder(print); |
||
print("*** postorder ***"); tree.postorder(print); |
print("*** postorder ***"); tree.postorder(print); |
||
print("*** levelorder ***"); tree.levelorder(print);</ |
print("*** levelorder ***"); tree.levelorder(print);</syntaxhighlight> |
||
====Functional composition==== |
====Functional composition==== |
||
Line 6,015: | Line 6,015: | ||
(for binary trees consisting of nested lists) |
(for binary trees consisting of nested lists) |
||
< |
<syntaxhighlight lang=javascript>(function () { |
||
function preorder(n) { |
function preorder(n) { |
||
Line 6,103: | Line 6,103: | ||
return wikiTable(lstTest, true) + '\n\n' + JSON.stringify(lstTest); |
return wikiTable(lstTest, true) + '\n\n' + JSON.stringify(lstTest); |
||
})();</ |
})();</syntaxhighlight> |
||
Output: |
Output: |
||
Line 6,120: | Line 6,120: | ||
|} |
|} |
||
< |
<syntaxhighlight lang=JavaScript>[["Traversal","Nodes visited"], |
||
["preorder",[1,2,4,7,5,3,6,8,9]],["inorder",[7,4,2,5,1,8,6,9,3]], |
["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]]]</ |
["postorder",[7,4,5,2,8,9,6,3,1]],["levelorder",[1,2,3,4,5,6,7,8,9]]]</syntaxhighlight> |
||
Line 6,132: | Line 6,132: | ||
< |
<syntaxhighlight lang=JavaScript>(function () { |
||
'use strict'; |
'use strict'; |
||
Line 6,252: | Line 6,252: | ||
}, {}); |
}, {}); |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
< |
<syntaxhighlight lang=JavaScript>{"preorder":[1, 2, 4, 7, 5, 3, 6, 8, 9], |
||
"inorder":[7, 4, 2, 5, 1, 8, 6, 9, 3], |
"inorder":[7, 4, 2, 5, 1, 8, 6, 9, 3], |
||
"postorder":[7, 4, 5, 2, 8, 9, 6, 3, 1], |
"postorder":[7, 4, 5, 2, 8, 9, 6, 3, 1], |
||
"level-order":[1, 2, 3, 4, 5, 6, 7, 8, 9]}</ |
"level-order":[1, 2, 3, 4, 5, 6, 7, 8, 9]}</syntaxhighlight> |
||
===ES6=== |
===ES6=== |
||
Line 6,263: | Line 6,263: | ||
{{Trans|Haskell}} |
{{Trans|Haskell}} |
||
{{Trans|Python}} |
{{Trans|Python}} |
||
< |
<syntaxhighlight lang=JavaScript>(() => { |
||
"use strict"; |
"use strict"; |
||
Line 6,309: | Line 6,309: | ||
// task: 'Visualize a tree' |
// task: 'Visualize a tree' |
||
console.log([ |
console.log([ |
||
" |
" + 4 - 7", |
||
" |
" + 2 ¦", |
||
" |
" ¦ + 5", |
||
" 1 |
" 1 ¦", |
||
" |
" ¦ + 8", |
||
" |
" + 3 - 6 ¦", |
||
" |
" + 9" |
||
].join("\n")); |
].join("\n")); |
||
Line 6,390: | Line 6,390: | ||
// MAIN --- |
// MAIN --- |
||
return main(); |
return main(); |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> + 4 - 7 |
||
+ 2 ¦ |
|||
¦ + 5 |
|||
1 |
1 ¦ |
||
¦ + 8 |
|||
+ 3 - 6 ¦ |
|||
+ 9 |
|||
preorder: 1,2,4,7,5,3,6,8,9 |
preorder: 1,2,4,7,5,3,6,8,9 |
||
inorder: 7,4,2,5,1,8,6,9,3 |
inorder: 7,4,2,5,1,8,6,9,3 |
||
Line 6,408: | Line 6,408: | ||
The implementation assumes an array structured recursively as [ node, left, right ], where "left" and "right" may be [] or null equivalently. |
The implementation assumes an array structured recursively as [ node, left, right ], where "left" and "right" may be [] or null equivalently. |
||
< |
<syntaxhighlight lang=jq>def preorder: |
||
if length == 0 then empty |
if length == 0 then empty |
||
else .[0], (.[1]|preorder), (.[2]|preorder) |
else .[0], (.[1]|preorder), (.[2]|preorder) |
||
Line 6,434: | Line 6,434: | ||
def levelorder: [.] | recurse( tails ) | heads; |
def levelorder: [.] | recurse( tails ) | heads; |
||
</syntaxhighlight> |
|||
</lang> |
|||
'''The task''': |
'''The task''': |
||
< |
<syntaxhighlight lang=jq>def task: |
||
# [node, left, right] |
# [node, left, right] |
||
def atree: [1, [2, [4, [7,[],[]], |
def atree: [1, [2, [4, [7,[],[]], |
||
Line 6,452: | Line 6,452: | ||
; |
; |
||
task</ |
task</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
$ jq -n -c -r -f Tree_traversal.jq |
$ jq -n -c -r -f Tree_traversal.jq |
||
Line 6,461: | Line 6,461: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang=Julia>tree = Any[1, Any[2, Any[4, Any[7, Any[], |
||
Any[]], |
Any[]], |
||
Any[]], |
Any[]], |
||
Line 6,487: | Line 6,487: | ||
t = mapreduce(x -> isa(x, Number) ? (f(x); []) : x, vcat, t) |
t = mapreduce(x -> isa(x, Number) ? (f(x); []) : x, vcat, t) |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
Line 6,502: | Line 6,502: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
===procedural style=== |
===procedural style=== |
||
< |
<syntaxhighlight lang=scala>data class Node(val v: Int, var left: Node? = null, var right: Node? = null) { |
||
override fun toString() = "$v" |
override fun toString() = "$v" |
||
} |
} |
||
Line 6,568: | Line 6,568: | ||
exec(" postOrder: ", nodes[1], ::postOrder) |
exec(" postOrder: ", nodes[1], ::postOrder) |
||
exec("level-order: ", nodes[1], ::levelOrder) |
exec("level-order: ", nodes[1], ::levelOrder) |
||
}</ |
}</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 6,579: | Line 6,579: | ||
===object-oriented style=== |
===object-oriented style=== |
||
< |
<syntaxhighlight lang=scala>fun main(args: Array<String>) { |
||
data class Node(val v: Int, var left: Node? = null, var right: Node? = null) { |
data class Node(val v: Int, var left: Node? = null, var right: Node? = null) { |
||
override fun toString() = " $v" |
override fun toString() = " $v" |
||
Line 6,620: | Line 6,620: | ||
exec("level-order:", Node::levelOrder) |
exec("level-order:", Node::levelOrder) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Lambdatalk}}== |
=={{header|Lambdatalk}}== |
||
Line 6,633: | Line 6,633: | ||
- {A.get index array} gets the value of array at index |
- {A.get index array} gets the value of array at index |
||
</pre> |
</pre> |
||
< |
<syntaxhighlight lang=scheme> |
||
{def walk |
{def walk |
||
Line 6,668: | Line 6,668: | ||
{sort < {T}} -> 1 2 3 4 5 6 7 8 9 |
{sort < {T}} -> 1 2 3 4 5 6 7 8 9 |
||
{sort > {T}} -> 9 8 7 6 5 4 3 2 1 |
{sort > {T}} -> 9 8 7 6 5 4 3 2 1 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Lingo}}== |
=={{header|Lingo}}== |
||
< |
<syntaxhighlight lang=lingo>-- parent script "BinaryTreeNode" |
||
property _val, _left, _right |
property _val, _left, _right |
||
Line 6,698: | Line 6,698: | ||
on getRight (me) |
on getRight (me) |
||
return me._right |
return me._right |
||
end</ |
end</syntaxhighlight> |
||
< |
<syntaxhighlight lang=lingo>-- parent script "BinaryTreeTraversal" |
||
on inOrder (me, node, l) |
on inOrder (me, node, l) |
||
Line 6,750: | Line 6,750: | ||
delete the last char of str |
delete the last char of str |
||
return str |
return str |
||
end</ |
end</syntaxhighlight> |
||
Usage: |
Usage: |
||
< |
<syntaxhighlight lang=lingo>-- create the tree |
||
l = [] |
l = [] |
||
repeat with i = 1 to 10 |
repeat with i = 1 to 10 |
||
Line 6,772: | Line 6,772: | ||
put "inorder: " & trav.serialize(trav.inOrder(l[1])) |
put "inorder: " & trav.serialize(trav.inOrder(l[1])) |
||
put "postorder: " & trav.serialize(trav.postOrder(l[1])) |
put "postorder: " & trav.serialize(trav.postOrder(l[1])) |
||
put "level-order: " & trav.serialize(trav.levelOrder(l[1]))</ |
put "level-order: " & trav.serialize(trav.levelOrder(l[1]))</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 6,783: | Line 6,783: | ||
=={{header|Logo}}== |
=={{header|Logo}}== |
||
< |
<syntaxhighlight lang=logo>; nodes are [data left right], use "first" to get data |
||
to node.left :node |
to node.left :node |
||
Line 6,839: | Line 6,839: | ||
in.order :tree [(type ? "| |)] (print) |
in.order :tree [(type ? "| |)] (print) |
||
post.order :tree [(type ? "| |)] (print) |
post.order :tree [(type ? "| |)] (print) |
||
level.order :tree [(type ? "| |)] (print)</ |
level.order :tree [(type ? "| |)] (print)</syntaxhighlight> |
||
=={{header|Logtalk}}== |
=={{header|Logtalk}}== |
||
< |
<syntaxhighlight lang=logtalk> |
||
:- object(tree_traversal). |
:- object(tree_traversal). |
||
Line 6,923: | Line 6,923: | ||
:- end_object. |
:- end_object. |
||
</syntaxhighlight> |
|||
</lang> |
|||
Sample output: |
Sample output: |
||
< |
<syntaxhighlight lang=text> |
||
| ?- ?- tree_traversal::orders. |
| ?- ?- tree_traversal::orders. |
||
Pre-order: 1 2 4 7 5 3 6 8 9 |
Pre-order: 1 2 4 7 5 3 6 8 9 |
||
Line 6,932: | Line 6,932: | ||
Level-order: 1 2 3 4 5 6 7 8 9 |
Level-order: 1 2 3 4 5 6 7 8 9 |
||
yes |
yes |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
< |
<syntaxhighlight lang=Lua>-- Utility |
||
local function append(t1, t2) |
local function append(t1, t2) |
||
for _, v in ipairs(t2) do |
for _, v in ipairs(t2) do |
||
Line 6,980: | Line 6,980: | ||
print("inorder: " .. table.concat(tree:order({2, 1, 3}), " ")) |
print("inorder: " .. table.concat(tree:order({2, 1, 3}), " ")) |
||
print("postorder: " .. table.concat(tree:order({2, 3, 1}), " ")) |
print("postorder: " .. table.concat(tree:order({2, 3, 1}), " ")) |
||
print("level-order: " .. table.concat(tree:levelorder(), " "))</ |
print("level-order: " .. table.concat(tree:levelorder(), " "))</syntaxhighlight> |
||
=={{header|M2000 Interpreter}}== |
=={{header|M2000 Interpreter}}== |
||
Line 6,986: | Line 6,986: | ||
A tuple is an "auto array" in M2000 Interpreter. (,) is the zero length array. |
A tuple is an "auto array" in M2000 Interpreter. (,) is the zero length array. |
||
< |
<syntaxhighlight lang=M2000 Interpreter> |
||
Module CheckIt { |
Module CheckIt { |
||
Null=(,) |
Null=(,) |
||
Line 7,046: | Line 7,046: | ||
} |
} |
||
CheckIt |
CheckIt |
||
</syntaxhighlight> |
|||
</lang> |
|||
===Using OOP=== |
===Using OOP=== |
||
Now tree is nodes with pointers to nodes (a node ifs a Group, the user object) |
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. |
The "as pointer" is optional, but we can use type check if we want. |
||
< |
<syntaxhighlight lang=M2000 Interpreter> |
||
Module OOP { |
Module OOP { |
||
\\ Class is a global function (until this module end) |
\\ Class is a global function (until this module end) |
||
Line 7,135: | Line 7,135: | ||
} |
} |
||
OOP |
OOP |
||
</syntaxhighlight> |
|||
</lang> |
|||
or we can put modules inside Node Class as methods |
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) |
also i put a visitor as a call back (a lambda function called as module) |
||
< |
<syntaxhighlight lang=M2000 Interpreter> |
||
Module OOP { |
Module OOP { |
||
\\ Class is a global function (until this module end) |
\\ Class is a global function (until this module end) |
||
Line 7,227: | Line 7,227: | ||
} |
} |
||
OOP |
OOP |
||
</syntaxhighlight> |
|||
</lang> |
|||
Using Event object as visitor |
Using Event object as visitor |
||
< |
<syntaxhighlight lang=M2000 Interpreter> |
||
Module OOP { |
Module OOP { |
||
\\ Class is a global function (until this module end) |
\\ Class is a global function (until this module end) |
||
Line 7,322: | Line 7,322: | ||
} |
} |
||
OOP |
OOP |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 7,333: | Line 7,333: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang=mathematica>preorder[a_Integer] := a; |
||
preorder[a_[b__]] := Flatten@{a, preorder /@ {b}}; |
preorder[a_[b__]] := Flatten@{a, preorder /@ {b}}; |
||
inorder[a_Integer] := a; |
inorder[a_Integer] := a; |
||
Line 7,341: | Line 7,341: | ||
levelorder[a_] := |
levelorder[a_] := |
||
Flatten[Table[Level[a, {n}], {n, 0, Depth@a}]] /. {b_Integer[__] :> |
Flatten[Table[Level[a, {n}], {n, 0, Depth@a}]] /. {b_Integer[__] :> |
||
b};</ |
b};</syntaxhighlight> |
||
Example: |
Example: |
||
< |
<syntaxhighlight lang=mathematica>preorder[1[2[4[7], 5], 3[6[8, 9]]]] |
||
inorder[1[2[4[7], 5], 3[6[8, 9]]]] |
inorder[1[2[4[7], 5], 3[6[8, 9]]]] |
||
postorder[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]]]]</ |
levelorder[1[2[4[7], 5], 3[6[8, 9]]]]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{1, 2, 4, 7, 5, 3, 6, 8, 9} |
<pre>{1, 2, 4, 7, 5, 3, 6, 8, 9} |
||
Line 7,355: | Line 7,355: | ||
=={{header|Mercury}}== |
=={{header|Mercury}}== |
||
< |
<syntaxhighlight lang=mercury>:- module tree_traversal. |
||
:- interface. |
:- interface. |
||
Line 7,447: | Line 7,447: | ||
print_value(V, !IO) :- |
print_value(V, !IO) :- |
||
io.print(V, !IO), |
io.print(V, !IO), |
||
io.write_string(" ", !IO).</ |
io.write_string(" ", !IO).</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>preorder: 1 2 4 7 5 3 6 8 9 |
<pre>preorder: 1 2 4 7 5 3 6 8 9 |
||
Line 7,455: | Line 7,455: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang=nim>import deques |
||
type |
type |
||
Line 7,499: | Line 7,499: | ||
echo inorder tree |
echo inorder tree |
||
echo postorder tree |
echo postorder tree |
||
echo levelorder tree</ |
echo levelorder tree</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 7,508: | Line 7,508: | ||
=={{header|Objeck}}== |
=={{header|Objeck}}== |
||
< |
<syntaxhighlight lang=objeck> |
||
??use Collection; |
|||
class Test { |
class Test { |
||
Line 7,621: | Line 7,621: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
Line 7,632: | Line 7,632: | ||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
< |
<syntaxhighlight lang=ocaml>type 'a tree = Empty |
||
| Node of 'a * 'a tree * 'a tree |
| Node of 'a * 'a tree * 'a tree |
||
Line 7,681: | Line 7,681: | ||
inorder (Printf.printf "%d ") tree; print_newline (); |
inorder (Printf.printf "%d ") tree; print_newline (); |
||
postorder (Printf.printf "%d ") tree; print_newline (); |
postorder (Printf.printf "%d ") tree; print_newline (); |
||
levelorder (Printf.printf "%d ") tree; print_newline ()</ |
levelorder (Printf.printf "%d ") tree; print_newline ()</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>1 2 4 7 5 3 6 8 9 |
<pre>1 2 4 7 5 3 6 8 9 |
||
Line 7,690: | Line 7,690: | ||
=={{header|Oforth}}== |
=={{header|Oforth}}== |
||
< |
<syntaxhighlight lang=Oforth>Object Class new: Tree(v, l, r) |
||
Tree method: initialize(v, l, r) v := v l := l r := r ; |
Tree method: initialize(v, l, r) v := v l := l r := r ; |
||
Line 7,720: | Line 7,720: | ||
n l dup ifNotNull: [ c send ] drop |
n l dup ifNotNull: [ c send ] drop |
||
n r dup ifNotNull: [ c send ] drop |
n r dup ifNotNull: [ c send ] drop |
||
] ;</ |
] ;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 7,743: | Line 7,743: | ||
=={{header|ooRexx}}== |
=={{header|ooRexx}}== |
||
< |
<syntaxhighlight lang=ooRexx> |
||
one = .Node~new(1); |
one = .Node~new(1); |
||
two = .Node~new(2); |
two = .Node~new(2); |
||
Line 7,827: | Line 7,827: | ||
nodequeue~queue(next~right) |
nodequeue~queue(next~right) |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 7,837: | Line 7,837: | ||
=={{header|Oz}}== |
=={{header|Oz}}== |
||
< |
<syntaxhighlight lang=oz>declare |
||
Tree = n(1 |
Tree = n(1 |
||
n(2 |
n(2 |
||
Line 7,894: | Line 7,894: | ||
{Show {Inorder Tree}} |
{Show {Inorder Tree}} |
||
{Show {Postorder Tree}} |
{Show {Postorder Tree}} |
||
{Show {Levelorder Tree}}</ |
{Show {Levelorder Tree}}</syntaxhighlight> |
||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
Tree nodes are represented by 3-element arrays: [0] - the value; [1] - left child; [2] - right child. |
Tree nodes are represented by 3-element arrays: [0] - the value; [1] - left child; [2] - right child. |
||
< |
<syntaxhighlight lang=perl>sub preorder |
||
{ |
{ |
||
my $t = shift or return (); |
my $t = shift or return (); |
||
Line 7,933: | Line 7,933: | ||
print "in: @{[inorder($x)]}\n"; |
print "in: @{[inorder($x)]}\n"; |
||
print "post: @{[postorder($x)]}\n"; |
print "post: @{[postorder($x)]}\n"; |
||
print "depth: @{[depth($x)]}\n";</ |
print "depth: @{[depth($x)]}\n";</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>pre: 1 2 4 7 5 3 6 8 9 |
<pre>pre: 1 2 4 7 5 3 6 8 9 |
||
Line 7,945: | Line 7,945: | ||
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. |
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. |
||
<!--< |
<!--<syntaxhighlight lang=Phix>--> |
||
<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> |
<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,992: | Line 7,992: | ||
<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 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> |
<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> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
Line 8,003: | Line 8,003: | ||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
< |
<syntaxhighlight lang=PHP>class Node { |
||
private $left; |
private $left; |
||
private $right; |
private $right; |
||
Line 8,104: | Line 8,104: | ||
$tree->postOrder($arr[1]); |
$tree->postOrder($arr[1]); |
||
echo "\nlevel-order:\t"; |
echo "\nlevel-order:\t"; |
||
$tree->levelOrder($arr[1]);</ |
$tree->levelOrder($arr[1]);</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>preorder: 1 2 4 7 5 3 6 8 9 |
<pre>preorder: 1 2 4 7 5 3 6 8 9 |
||
Line 8,112: | Line 8,112: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang=PicoLisp>(de preorder (Node Fun) |
||
(when Node |
(when Node |
||
(Fun (car Node)) |
(Fun (car Node)) |
||
Line 8,145: | Line 8,145: | ||
(prin (align -13 (pack Order ":"))) |
(prin (align -13 (pack Order ":"))) |
||
(Order *Tree printsp) |
(Order *Tree printsp) |
||
(prinl) )</ |
(prinl) )</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>preorder: 1 2 4 7 5 3 6 8 9 |
<pre>preorder: 1 2 4 7 5 3 6 8 9 |
||
Line 8,154: | Line 8,154: | ||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
Works with SWI-Prolog. |
Works with SWI-Prolog. |
||
< |
<syntaxhighlight lang=Prolog>tree :- |
||
Tree= [1, |
Tree= [1, |
||
[2, |
[2, |
||
Line 8,210: | Line 8,210: | ||
append_dl(X-Y, Y-Z, X-Z). |
append_dl(X-Y, Y-Z, X-Z). |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output : |
Output : |
||
<pre>?- tree. |
<pre>?- tree. |
||
Line 8,222: | Line 8,222: | ||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
{{works with|PureBasic|4.5+}} |
{{works with|PureBasic|4.5+}} |
||
< |
<syntaxhighlight lang=PureBasic>Structure node |
||
value.i |
value.i |
||
*left.node |
*left.node |
||
Line 8,356: | Line 8,356: | ||
Input() |
Input() |
||
CloseConsole() |
CloseConsole() |
||
EndIf</ |
EndIf</syntaxhighlight> |
||
Sample output: |
Sample output: |
||
<pre>preorder: 1 2 4 7 5 3 6 8 9 |
<pre>preorder: 1 2 4 7 5 3 6 8 9 |
||
Line 8,367: | Line 8,367: | ||
===Python: Procedural=== |
===Python: Procedural=== |
||
< |
<syntaxhighlight lang=python>from collections import namedtuple |
||
Node = namedtuple('Node', 'data, left, right') |
Node = namedtuple('Node', 'data, left, right') |
||
Line 8,438: | Line 8,438: | ||
print(f"{traversal.__name__:>{w}}:", end=' ') |
print(f"{traversal.__name__:>{w}}:", end=' ') |
||
traversal(tree) |
traversal(tree) |
||
print()</ |
print()</syntaxhighlight> |
||
'''Sample output:''' |
'''Sample output:''' |
||
Line 8,454: | Line 8,454: | ||
Subclasses a namedtuple adding traversal methods that apply a visitor function to data at nodes of the tree in order |
Subclasses a namedtuple adding traversal methods that apply a visitor function to data at nodes of the tree in order |
||
< |
<syntaxhighlight lang=python>from collections import namedtuple |
||
from sys import stdout |
from sys import stdout |
||
Line 8,514: | Line 8,514: | ||
stdout.write('\nlevelorder: ') |
stdout.write('\nlevelorder: ') |
||
tree.levelorder(printwithspace) |
tree.levelorder(printwithspace) |
||
stdout.write('\n')</ |
stdout.write('\n')</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 8,531: | Line 8,531: | ||
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. |
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. |
||
< |
<syntaxhighlight lang=python>'''Tree traversals''' |
||
from itertools import chain |
from itertools import chain |
||
Line 8,741: | Line 8,741: | ||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>Tree traversals - accumulating and folding: |
<pre>Tree traversals - accumulating and folding: |
||
Line 8,758: | Line 8,758: | ||
=={{header|Qi}}== |
=={{header|Qi}}== |
||
<syntaxhighlight lang=qi> |
|||
<lang qi> |
|||
(set *tree* [1 [2 [4 [7]] |
(set *tree* [1 [2 [4 [7]] |
||
[5]] |
[5]] |
||
Line 8,803: | Line 8,803: | ||
(inorder (value *tree*)) |
(inorder (value *tree*)) |
||
(levelorder (value *tree*)) |
(levelorder (value *tree*)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
Line 8,815: | Line 8,815: | ||
Requires the words at [[Queue/Definition#Quackery]] for <code>level-order</code>. |
Requires the words at [[Queue/Definition#Quackery]] for <code>level-order</code>. |
||
< |
<syntaxhighlight lang=Quackery> [ this ] is nil ( --> [ ) |
||
[ ' [ 1 |
[ ' [ 1 |
||
Line 8,861: | Line 8,861: | ||
tree in-order cr |
tree in-order cr |
||
tree post-order cr |
tree post-order cr |
||
tree level-order cr</ |
tree level-order cr</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 8,872: | Line 8,872: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang=racket> |
||
#lang racket |
#lang racket |
||
Line 8,895: | Line 8,895: | ||
(define (run order) |
(define (run order) |
||
(printf "~a:" (object-name order)) |
(printf "~a:" (object-name order)) |
||
(order the-tree ( |
(order the-tree (?(x) (printf " ~s" x))) |
||
(newline)) |
(newline)) |
||
(for-each run (list preorder inorder postorder levelorder)) |
(for-each run (list preorder inorder postorder levelorder)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
Line 8,910: | Line 8,910: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
(formerly Perl 6) |
(formerly Perl 6) |
||
< |
<syntaxhighlight lang=perl6>class TreeNode { |
||
has TreeNode $.parent; |
has TreeNode $.parent; |
||
has TreeNode $.left; |
has TreeNode $.left; |
||
Line 8,967: | Line 8,967: | ||
say "inorder: ",$root.in-order.join(" "); |
say "inorder: ",$root.in-order.join(" "); |
||
say "postorder: ",$root.post-order.join(" "); |
say "postorder: ",$root.post-order.join(" "); |
||
say "levelorder:",$root.level-order.join(" ");</ |
say "levelorder:",$root.level-order.join(" ");</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>preorder: 1 2 4 7 5 3 6 8 9 |
<pre>preorder: 1 2 4 7 5 3 6 8 9 |
||
Line 8,975: | Line 8,975: | ||
=={{header|REBOL}}== |
=={{header|REBOL}}== |
||
< |
<syntaxhighlight lang=REBOL> |
||
tree: [1 [2 [4 [7 [] []] []] [5 [] []]] [3 [6 [8 [] []] [9 [] []]] []]] |
tree: [1 [2 [4 [7 [] []] []] [5 [] []]] [3 [6 [8 [] []] [9 [] []]] []]] |
||
; "compacted" version |
; "compacted" version |
||
Line 9,022: | Line 9,022: | ||
] |
] |
||
prin "level-order: " level-order tree |
prin "level-order: " level-order tree |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 9,032: | Line 9,032: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
< |
<syntaxhighlight lang=rexx> |
||
/* REXX *************************************************************** |
/* REXX *************************************************************** |
||
* Tree traversal |
* Tree traversal |
||
Line 9,350: | Line 9,350: | ||
Say '' |
Say '' |
||
End |
End |
||
Return</ |
Return</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 1 |
<pre> 1 |
||
Line 9,366: | Line 9,366: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang=ruby>BinaryTreeNode = Struct.new(:value, :left, :right) do |
||
def self.from_array(nested_list) |
def self.from_array(nested_list) |
||
value, left, right = nested_list |
value, left, right = nested_list |
||
Line 9,405: | Line 9,405: | ||
root.send(mthd) {|node| print "#{node.value} "} |
root.send(mthd) {|node| print "#{node.value} "} |
||
puts |
puts |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 9,416: | Line 9,416: | ||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
This solution uses iteration (rather than recursion) for all traversal types. |
This solution uses iteration (rather than recursion) for all traversal types. |
||
< |
<syntaxhighlight lang=Rust> |
||
#![feature(box_syntax, box_patterns)] |
#![feature(box_syntax, box_patterns)] |
||
Line 9,592: | Line 9,592: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output is same as Ruby et al. |
Output is same as Ruby et al. |
||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
{{works with|Scala|2.11.x}} |
{{works with|Scala|2.11.x}} |
||
< |
<syntaxhighlight lang=Scala>case class IntNode(value: Int, left: Option[IntNode] = None, right: Option[IntNode] = None) { |
||
def preorder(f: IntNode => Unit) { |
def preorder(f: IntNode => Unit) { |
||
Line 9,651: | Line 9,651: | ||
println(s) |
println(s) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Output:<pre> |
Output:<pre> |
||
Line 9,661: | Line 9,661: | ||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
< |
<syntaxhighlight lang=scheme>(define (preorder tree) |
||
(if (null? tree) |
(if (null? tree) |
||
'() |
'() |
||
Line 9,726: | Line 9,726: | ||
()))) |
()))) |
||
(demonstration the-task-tree)</ |
(demonstration the-task-tree)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>preorder: 1 2 4 7 5 3 6 8 9 |
<pre>preorder: 1 2 4 7 5 3 6 8 9 |
||
Line 9,734: | Line 9,734: | ||
=={{header|SequenceL}}== |
=={{header|SequenceL}}== |
||
< |
<syntaxhighlight lang=sequenceL> |
||
main(args(2)) := |
main(args(2)) := |
||
"preorder: " ++ toString(preOrder(testTree)) ++ |
"preorder: " ++ toString(preOrder(testTree)) ++ |
||
Line 9,777: | Line 9,777: | ||
) |
) |
||
); |
); |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Output: |
Output: |
||
Line 9,789: | Line 9,789: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Perl}} |
{{trans|Perl}} |
||
< |
<syntaxhighlight lang=ruby>func preorder(t) { |
||
t ? [t[0], __FUNC__(t[1])..., __FUNC__(t[2])...] : []; |
t ? [t[0], __FUNC__(t[1])..., __FUNC__(t[2])...] : []; |
||
} |
} |
||
Line 9,816: | Line 9,816: | ||
say "in: #{inorder(x)}"; |
say "in: #{inorder(x)}"; |
||
say "post: #{postorder(x)}"; |
say "post: #{postorder(x)}"; |
||
say "depth: #{depth(x)}";</ |
say "depth: #{depth(x)}";</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 9,835: | Line 9,835: | ||
'''Object subclass: EmptyNode''' |
'''Object subclass: EmptyNode''' |
||
< |
<syntaxhighlight lang=smalltalk>"Protocol: visiting" |
||
EmptyNode>>accept: aVisitor |
EmptyNode>>accept: aVisitor |
||
Line 9,844: | Line 9,844: | ||
EmptyNode>>traverse: aVisitorClass do: aBlock |
EmptyNode>>traverse: aVisitorClass do: aBlock |
||
^self accept: (aVisitorClass block: aBlock) |
^self accept: (aVisitorClass block: aBlock) |
||
</syntaxhighlight> |
|||
</lang> |
|||
'''EmptyNode subclass: Node''' |
'''EmptyNode subclass: Node''' |
||
< |
<syntaxhighlight lang=smalltalk>"Protocol: visiting" |
||
Node>>accept: aVisitor |
Node>>accept: aVisitor |
||
^aVisitor visit: self |
^aVisitor visit: self |
||
Line 9,882: | Line 9,882: | ||
Node class>>data: anObject |
Node class>>data: anObject |
||
^self new data: anObject |
^self new data: anObject |
||
</syntaxhighlight> |
|||
</lang> |
|||
'''Object subclass: Visitor''' |
'''Object subclass: Visitor''' |
||
< |
<syntaxhighlight lang=smalltalk>"Protocol: visiting" |
||
visit: aNode |
visit: aNode |
||
self subclassResponsibility |
self subclassResponsibility |
||
Line 9,902: | Line 9,902: | ||
Visitor class>>block: aBlock |
Visitor class>>block: aBlock |
||
^self new block: aBlock |
^self new block: aBlock |
||
</syntaxhighlight> |
|||
</lang> |
|||
'''Visitor subclass: InOrder''' |
'''Visitor subclass: InOrder''' |
||
< |
<syntaxhighlight lang=smalltalk>"Protocol: visiting" |
||
InOrder>>visit: aNode |
InOrder>>visit: aNode |
||
aNode left accept: self. |
aNode left accept: self. |
||
block value: aNode. |
block value: aNode. |
||
aNode right accept: self |
aNode right accept: self |
||
</syntaxhighlight> |
|||
</lang> |
|||
'''Visitor subclass: LevelOrder''' |
'''Visitor subclass: LevelOrder''' |
||
< |
<syntaxhighlight lang=smalltalk>"Protocol: visiting" |
||
LevelOrder>>visit: aNode |
LevelOrder>>visit: aNode |
||
| queue | |
| queue | |
||
Line 9,925: | Line 9,925: | ||
add: aNode right; |
add: aNode right; |
||
yourself |
yourself |
||
</syntaxhighlight> |
|||
</lang> |
|||
'''Visitor subclass: PostOrder''' |
'''Visitor subclass: PostOrder''' |
||
< |
<syntaxhighlight lang=smalltalk>"Protocol: visiting" |
||
PostOrder>>visit: aNode |
PostOrder>>visit: aNode |
||
aNode left accept: self. |
aNode left accept: self. |
||
aNode right accept: self. |
aNode right accept: self. |
||
block value: aNode |
block value: aNode |
||
</syntaxhighlight> |
|||
</lang> |
|||
"Visitor subclass: PreOrder" |
"Visitor subclass: PreOrder" |
||
< |
<syntaxhighlight lang=smalltalk>"Protocol: visiting" |
||
PreOrder>>visit: aNode |
PreOrder>>visit: aNode |
||
block value: aNode. |
block value: aNode. |
||
aNode left accept: self. |
aNode left accept: self. |
||
aNode right accept: self |
aNode right accept: self |
||
</syntaxhighlight> |
|||
</lang> |
|||
Execute code in a Workspace: |
Execute code in a Workspace: |
||
< |
<syntaxhighlight lang=smalltalk>| tree | |
||
tree := (Node data: 1) |
tree := (Node data: 1) |
||
left: ((Node data: 2) |
left: ((Node data: 2) |
||
Line 9,962: | Line 9,962: | ||
tree traverse: LevelOrder do: [:node | Transcript print: node data; space]. |
tree traverse: LevelOrder do: [:node | Transcript print: node data; space]. |
||
Transcript cr. |
Transcript cr. |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output in Transcript: |
Output in Transcript: |
||
Line 9,971: | Line 9,971: | ||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
< |
<syntaxhighlight lang=swift>class TreeNode<T> { |
||
let value: T |
let value: T |
||
let left: TreeNode? |
let left: TreeNode? |
||
Line 10,056: | Line 10,056: | ||
print("level-order: ", terminator: "") |
print("level-order: ", terminator: "") |
||
n.levelOrder(function: fn) |
n.levelOrder(function: fn) |
||
print()</ |
print()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 10,068: | Line 10,068: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
{{works with|Tcl|8.6}} or {{libheader|TclOO}} |
{{works with|Tcl|8.6}} or {{libheader|TclOO}} |
||
< |
<syntaxhighlight lang=tcl>oo::class create tree { |
||
# Basic tree data structure stuff... |
# Basic tree data structure stuff... |
||
variable val l r |
variable val l r |
||
Line 10,117: | Line 10,117: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
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. |
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: |
Demo code to satisfy the official challenge instance: |
||
< |
<syntaxhighlight lang=tcl># Helpers to make construction and listing of a whole tree simpler |
||
proc Tree nested { |
proc Tree nested { |
||
lassign $nested v l r |
lassign $nested v l r |
||
Line 10,142: | Line 10,142: | ||
puts "postorder: [Listify $t postorder]" |
puts "postorder: [Listify $t postorder]" |
||
puts "level-order: [Listify $t levelorder]" |
puts "level-order: [Listify $t levelorder]" |
||
$t destroy</ |
$t destroy</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>preorder: 1 2 4 7 5 3 6 8 9 |
<pre>preorder: 1 2 4 7 5 3 6 8 9 |
||
Line 10,151: | Line 10,151: | ||
=={{header|UNIX Shell}}== |
=={{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. |
Bash (also "sh" on most Unix systems) has arrays. We implement a node as an association between three arrays: left, right, and value. |
||
< |
<syntaxhighlight lang=bash>left=() |
||
right=() |
right=() |
||
value=() |
value=() |
||
Line 10,234: | Line 10,234: | ||
inorder 1 |
inorder 1 |
||
postorder 1 |
postorder 1 |
||
levelorder 1</ |
levelorder 1</syntaxhighlight> |
||
The output: |
The output: |
||
< |
<syntaxhighlight lang=bash>preorder: 1 2 4 7 5 3 6 8 9 |
||
inorder: 7 4 2 5 1 8 6 9 3 |
inorder: 7 4 2 5 1 8 6 9 3 |
||
postorder: 7 4 5 2 8 9 6 3 1 |
postorder: 7 4 5 2 8 9 6 3 1 |
||
level-order: 1 2 3 4 5 6 7 8 9</ |
level-order: 1 2 3 4 5 6 7 8 9</syntaxhighlight> |
||
=={{header|Ursala}}== |
=={{header|Ursala}}== |
||
Line 10,251: | Line 10,251: | ||
the result on standard output as a |
the result on standard output as a |
||
list of lists of naturals. |
list of lists of naturals. |
||
< |
<syntaxhighlight lang=Ursala>tree = |
||
1^:< |
1^:< |
||
Line 10,264: | Line 10,264: | ||
#cast %nLL |
#cast %nLL |
||
main = <.pre,in,post,lev> tree</ |
main = <.pre,in,post,lev> tree</syntaxhighlight> |
||
output: |
output: |
||
<pre> |
<pre> |
||
Line 10,276: | Line 10,276: | ||
=={{header|VBA}}== |
=={{header|VBA}}== |
||
TreeItem Class Module |
TreeItem Class Module |
||
<syntaxhighlight lang=VB> |
|||
<lang VB> |
|||
Public Value As Integer |
Public Value As Integer |
||
Public LeftChild As TreeItem |
Public LeftChild As TreeItem |
||
Public RightChild As TreeItem |
Public RightChild As TreeItem |
||
</syntaxhighlight> |
|||
</lang> |
|||
Module |
Module |
||
<syntaxhighlight lang=VB> |
|||
<lang VB> |
|||
Dim tihead As TreeItem |
Dim tihead As TreeItem |
||
Line 10,354: | Line 10,354: | ||
Call LevelOrder(tihead) |
Call LevelOrder(tihead) |
||
End Sub |
End Sub |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 10,366: | Line 10,366: | ||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
The object-oriented version. |
The object-oriented version. |
||
< |
<syntaxhighlight lang=ecmascript>class Node { |
||
construct new(v) { |
construct new(v) { |
||
_v = v |
_v = v |
||
Line 10,432: | Line 10,432: | ||
nodes[1].exec(" inOrder:", Fn.new { |n| n.inOrder() }) |
nodes[1].exec(" inOrder:", Fn.new { |n| n.inOrder() }) |
||
nodes[1].exec(" postOrder:", Fn.new { |n| n.postOrder() }) |
nodes[1].exec(" postOrder:", Fn.new { |n| n.postOrder() }) |
||
nodes[1].exec("level-order:", Fn.new { |n| n.levelOrder() })</ |
nodes[1].exec("level-order:", Fn.new { |n| n.levelOrder() })</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 10,443: | Line 10,443: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
< |
<syntaxhighlight lang=zkl>class Node{ var [mixin=Node]left,right; var v; |
||
fcn init(val,[Node]l=Void,[Node]r=Void) { v,left,right=vm.arglist } |
fcn init(val,[Node]l=Void,[Node]r=Void) { v,left,right=vm.arglist } |
||
} |
} |
||
Line 10,473: | Line 10,473: | ||
sink |
sink |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
It is easy to convert to lazy by replacing "sink.write" with "vm.yield" and wrapping the traversal with a Utils.Generator. |
It is easy to convert to lazy by replacing "sink.write" with "vm.yield" and wrapping the traversal with a Utils.Generator. |
||
< |
<syntaxhighlight lang=zkl>t:=BTree(Node(1, |
||
Node(2, |
Node(2, |
||
Node(4,Node(7)), |
Node(4,Node(7)), |
||
Line 10,485: | Line 10,485: | ||
t.inOrder() .apply("v").println(" inorder"); |
t.inOrder() .apply("v").println(" inorder"); |
||
t.postOrder() .apply("v").println(" postorder"); |
t.postOrder() .apply("v").println(" postorder"); |
||
t.levelOrder().apply("v").println(" level-order");</ |
t.levelOrder().apply("v").println(" level-order");</syntaxhighlight> |
||
The "apply("v")" extracts the contents of var v from each node. |
The "apply("v")" extracts the contents of var v from each node. |
||
{{out}} |
{{out}} |