Tree traversal: Difference between revisions

{{trans|Python: Class based}}

 

Int data

Node? left

.right = right

 

visitor(.data)

I .left != N

.right.preorder(visitor)

 

I .left != N

.left.inorder(visitor)

.right.inorder(visitor)

 

I .left != N

.left.postorder(visitor)

visitor(.data)

 

d[level].append(.data)

I .left != N

print(‘levelorder: ’, end' ‘’)

tree.levelorder(printwithspace)

 

{{out}}

levelorder: 1 2 3 4 5 6 7 8 9

</pre>

 

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program deftree64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

 

=={{header|ACL2}}==

(if (endp tree)

nil

(defun flatten-level (tree)

(let ((levels (flatten-level-r1 tree 0 nil)))

 

=={{header|Action!}}==

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}}

 

INCLUDE "D2:ALLOCATE.ACT" ;from the Action! Tool Kit. You must type 'SET EndProg=*' from the monitor after compiling, but before running this program!

 

DestroyTree(t)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Tree_traversal.png Screenshot from Atari 8-bit computer]

 

=={{header|Ada}}==

with Ada.Unchecked_Deallocation;

with Ada.Containers.Doubly_Linked_Lists;

New_Line;

Destroy_Tree(N);

 

=={{header|Agda}}==

open import Level using (Level)

 

data Tree {a} (A : Set a) : Set a where

leaf : Tree A

 

variable

A : Set a

 

preorder tr = go tr []

where

go leaf ys = ys

 

inorder tr = go tr []

where

go leaf ys = ys

 

postorder tr = go tr []

where

go leaf ys = ys

 

level-order tr = concat (go tr [])

where

go leaf qs = qs

 

example-tree =

node 1

leaf)

 

_ = refl

 

_ = refl

 

_ = refl

 

 

=={{header|ALGOL 68}}==

 

{{works with|ELLA ALGOL 68|Any (with appropriate job cards)}}

PROC value repr = (VALUE value)STRING: whole(value, 0);

 

 

destroy tree(node)

Output:

<pre>

 

Written in Dyalog APL with dfns.

These accept four arguments (they are operators, a.k.a. higher-order functions):

<pre>acc visit ___order children bintree</pre>

and empty childL or childR mean and absence of the corresponding child node.

 

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.

<pre>

1 2 4 7 5 3 6 8 9

7 4 2 5 1 8 6 9 3

7 4 5 2 8 9 6 3 1

1 2 3 4 5 6 7 8 9

</pre>

=={{header|AppleScript}}==

{{Trans|JavaScript}}(ES6)

-- Sample tree of integers

set tree to node(1, ¬

-- 'Visualize a Tree':

set strTree to unlines({¬

script tabulate

justifyRight(14, space, s & ": ") & unwords(xs)

end script

-- inorder :: a -> [[a]] -> [a]

on inorder(x, xs)

item 1 of xs & x & concat(rest of xs)

else

on foldTree(f)

script

script go

of map(go))

end script

end script

end foldTree

tell mReturn(contents of f)

repeat with x in xs

end repeat

end tell

set lng to length of xs

repeat with i from lng to 1 by -1

end repeat

return v

-- values of each level of the tree.

script go

tell a to set {h, t} to {item 1, rest}

else

{{root of node} & h} & foldr(go, t, nest of node)

end script

end levels

 

else

script

end script

end if

-- to each element of xs.

script

tell mReturn(f)

set lng to length of xs

set lst to {}

repeat with i from 1 to lng

end repeat

return lst

end tell

end script

end map

set ys to {}

repeat with i from 1 to n

if missing value is v then

return ys

tell mReturn(f)

repeat with i from 1 to lng

end repeat

return lst

end tell

{{Out}}

preorder: 1 2 4 7 5 3 6 8 9

inorder: 7 4 2 5 1 8 6 9 3

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

 

/* ARM assembly Raspberry PI */

iMagicNumber: .int 0xCCCCCCCD

 

{{output}}

<pre>

 

=={{header|ATS}}==

"share/atspre_staload.hats"

//

println! ("postorder:\t", postorder(t0));

println! ("level-order:\t", levelorder(t0));

 

{{out}}

=={{header|AutoHotkey}}==

{{works with|AutoHotkey_L|45}}

AddNode(Tree,2,4,5,2)

AddNode(Tree,3,6,0,3)

t .= i%Lev%, Lev++

Return t

 

=={{header|AWK}}==

function preorder(tree, node, res, child) {

if (node == "")

delete result

}

 

=={{header|Bracmat}}==

( tree

= 1

& out$("level-order:" levelorder$(!tree.))

&

 

=={{header|C}}==

#include <stdio.h>

 

 

return 0;

 

=={{header|C sharp}}==

using System.Collections.Generic;

using System.Linq;

Console.WriteLine("{0}:\t{1}", traversal.Method.Name, string.Join(" ", traversal()));

}

 

=={{header|C++}}==

{{libheader|Boost|1.39.0}}

 

#include <iostream>

#include <queue>

 

return 0;

 

===Array version===

 

using namespace std;

level_order(t);

cout << endl;

 

===Modern C++===

{{works with|C++14}}

#include <memory>

#include <queue>

n.level_order(print);

std::cout << '\n';

 

{{out}}

 

=={{header|Ceylon}}==

ArrayList

}

levelOrder(tree);

print("");

 

=={{header|Clojure}}==

(when node

(doseq [o order]

(print (format "%-12s" (str f ":")))

((resolve f) tree pr-node)

 

=={{header|CLU}}==

pre_order, post_order, in_order, level_order

branch = struct[left, right: bintree[T], val: T]

stream$puts(po, " " || int$unparse(i))

end

{{out}}

<pre>preorder: 1 2 4 7 5 3 6 8 9

 

=={{header|CoffeeScript}}==

# 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

test_walk "postorder"

test_walk "levelorder"

output

> coffee tree_traversal.coffee

preorder 1 2 4 7 5 3 6 8 9

postorder 7 4 5 2 8 9 6 3 1

levelorder 1 2 3 4 5 6 7 8 9

 

=={{header|Common Lisp}}==

 

(when node

(funcall f (first node))

(funcall traversal-function *tree* (lambda (value) (format t " ~A" value))))

 

 

Output:

=={{header|Coq}}==

 

Require Import List.

 

 

Fixpoint height (t: tree) : nat :=

 

Example leaf n : tree := {| value := n ; children := nil |}.

match c with

| nil => n :: nil

end.

 

| O => nil

| S fuel' =>

p ++ levelorder_forest fuel' f

end.

Compute postorder t9.

Compute levelorder t9.

 

=={{header|Crystal}}==

{{trans|C++}}

class Node(T)

property left : Nil | Node(T)

puts

 

Output:

<pre>

=={{header|D}}==

This code is long because it's very generic.

 

const final class Node(T) {

tree.levelOrder;

writeln;

{{out}}

<pre> preOrder: 1 2 4 7 5 3 6 8 9

{{trans|Haskell}}

Generic as the first version, but not lazy as the Haskell version.

T v;

Node* l, r;

writeln(postOrder(tree));

writeln(levelOrder(tree));

{{out}}

<pre>[1, 2, 4, 7, 5, 3, 6, 8, 9]

===Alternative Lazy Version===

This version is not complete, it lacks the level order visit.

 

const struct Tree(T) {

tree.inOrder.map!(t => t.value).writeln;

tree.postOrder.map!(t => t.value).writeln;

{{out}}

<pre>[1, 2, 4, 7, 5, 3, 6, 8, 9]

[7, 4, 2, 5, 1, 8, 6, 9, 3]

[7, 4, 5, 2, 8, 9, 6, 3, 1]</pre>

 

=={{header|E}}==

 

null],

[5, null, null]],

print("level-order:")

levelOrder(btree, fn v { print(" ", v) })

 

=={{header|Eiffel}}==

 

Void-Safety has been disabled for simplicity of the code.

description : "Application for tree traversal demonstration"

output : "[

end

 

description : "A simple node for a binary tree"

libraries : "Relies on LINKED_LIST from EiffelBase"

 

end

 

=={{header|Elena}}==

import extensions'routines;

import system'collections;

class Node

{

constructor new(int value)

LevelOrder = new Enumerable

{

Enumerator enumerator() = new Enumerator

bool next() = queue.isNotEmpty();

{

Node item := queue.pop();

console.printLine("Postorder :", tree.Postorder);

console.printLine("LevelOrder:", tree.LevelOrder)

{{out}}

<pre>

=={{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].

component BinaryTreeTraversals (Tree, Element);

type Tree;

];

end component BinaryTreeTraversals;

Tests

use BinaryTreeTraversals (Tree, integer);

 

{Item(Level_order(BT))}?

{ 1, 2, 3, 4, 5, 6, 7, 8, 9}

 

=={{header|Elixir}}==

{{trans|Erlang}}

defp tnode, do: {}

defp tnode(v), do: {:node, v, {}, {}}

end

 

 

{{out}}

 

=={{header|Erlang}}==

-export([main/0]).

-export([preorder/2, inorder/2, postorder/2, levelorder/2]).

inorder(F, Tree), ?NEWLINE,

postorder(F, Tree), ?NEWLINE,

 

Output:

 

=={{header|Euphoria}}==

 

constant tree = {1,

puts(1,"level-order: ")

level_order(tree)

 

Output:

 

=={{header|F_Sharp|F#}}==

open System.IO

 

printf "\nlevel-order: "

levelorder tree |> Seq.iter show

 

=={{header|Factor}}==

math.parser ;

IN: rosetta.tree-traversal

[ "levelorder: " write levelorder nl ]

[ "levelorder2: " write levelorder2 nl ]

 

=={{header|Fantom}}==

class Tree

{

}

}

 

Output:

 

=={{header|Forth}}==

: node ( l r data -- node ) here >r , , , r> ;

: leaf ( data -- node ) 0 0 rot node ;

cr ' . tree postorder \ 7 4 5 2 8 9 6 3 1

cr tree max-depth . \ 4

 

=={{header|Fortran}}==

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.

 

IF (STYLE.EQ."PRE") CALL OUT(HAS)

IF (LINKL(HAS).GT.0) CALL TARZAN(LINKL(HAS),STYLE)

IF (STYLE.EQ."IN") CALL OUT(HAS)

IF (LINKR(HAS).GT.0) CALL TARZAN(LINKR(HAS),STYLE)

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.

 

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.

 

DO GASP = 1,MAXLEVEL

CALL TARZAN(1,HOW)

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===

MODULE ARAUCARIA !Cunning crosswords, also.

INTEGER ENUFF !To suit the set example.

CALL JANE("LEVEL") !Alternatively...

END !So much for that.

===Output===

Alternately GORILLA-style, and JANE-style:

 

=={{header|FreeBASIC}}==

#define NULL 0

 

Wend

End Sub

{{out}}

<pre>

=={{header|FunL}}==

{{trans|Haskell}}

 

def

println( inorder(tree) )

println( postorder(tree) )

 

{{out}}

=={{header|Fōrmulæ}}==

 

 

 

 

=={{header|GFA Basic}}==

 

maxnodes%=100 ! set a limit to size of tree

content%=0 ! index of content field

WEND

RETURN

 

=={{header|Go}}==

{{trans|C}}

This is like many examples on this page.

 

import "fmt"

func visitor(value int) {

fmt.Print(value, " ")

{{out}}

<pre>

===Flat slice===

Alternative representation. Like Wikipedia [http://en.wikipedia.org/wiki/Binary_tree#Arrays Binary tree#Arrays]

 

import "fmt"

}

}

 

=={{header|Groovy}}==

Uses Groovy '''Node''' and '''NodeBuilder''' classes

preorder = { Node node ->

([node] + node.children().collect { preorder(it) }).flatten()

node

}

 

Verify that '''BinaryNodeBuilder''' will not allow a node to have more than 2 children

new BinaryNodeBuilder().'1' {

a {}

} catch (org.codehaus.groovy.transform.powerassert.PowerAssertionError e) {

println 'limited to binary tree\r\n'

 

Test case #1 (from the task definition)

// / \

// 2 3

'6' { '8' {}; '9' {} }

}

 

Test case #2 (tests single right child)

// / \

// 2 3

'6' { '8' {}; '9' {} }

}

 

Run tests:

println "preorder: ${preorder(tree).collect{it.name()}}"

println "preorder: ${tree.depthFirst().collect{it.name()}}"

}

test(tree1)

 

Output:

=={{header|Haskell}}==

===Left Right nodes===

 

data Tree a

([preorder, inorder, postorder, levelorder] <*> [tree])

where

{{Out}}

<pre> 1

 

{{Trans|Python}}

 

---------------------- TREE TRAVERSAL --------------------

Int -> [Int] -> Int

nodeCount = const (succ . sum)

treeDepth = const (succ . foldr max 1)

treeMax x xs = maximum (x : xs)

treeMin x xs = minimum (x : xs)

treeProduct x xs = x * product xs

treeSum x xs = x + sum xs

treeWidth _ [] = 1

treeWidth _ xs = sum xs

 

treeLeaves :: Tree a -> [a]

where

--------------------------- TEST -------------------------

tree :: Tree Int

justifyLeft, justifyRight :: Int -> Char -> String -> String

justifyLeft n c s = take n (s <> replicate n c)

<pre>1

|

 

=={{header|Icon}} and {{header|Unicon}}==

bTree := [1, [2, [4, [7]], [5]], [3, [6, [8], [9]]]]

showTree(bTree, preorder|inorder|postorder|levelorder)

}

}

 

Output:

 

=={{header|Isabelle}}==

imports Main

begin

 

definition example :: "int tree" where

Node

(Node

)"

 

"preorder Leaf = []"

| "preorder (Node l a r) = a # preorder l @ preorder r"

lemma "preorder example = [1, 2, 4, 7, 5, 3, 6, 8, 9]" by code_simp

 

"inorder Leaf = []"

| "inorder (Node l a r) = inorder l @ [a] @ inorder r"

lemma "inorder example = [7, 4, 2, 5, 1, 8, 6, 9, 3]" by code_simp

 

"postorder Leaf = []"

| "postorder (Node l a r) = postorder l @ postorder r @ [a]"

so we provide some help by defining what the size of a tree is.

›

"tree_size Leaf = 1"

| "tree_size (Node l _ r) = 1 + tree_size l + tree_size r"

 

"bfs [] = []"

| "bfs (Leaf#q) = bfs q"

by pat_completeness auto

termination bfs

 

"levelorder t = bfs [t]"

 

lemma "levelorder example = [1, 2, 3, 4, 5, 6, 7, 8, 9]" by code_simp

 

 

=={{header|J}}==

 

postorder=: ([:; postorder&.>@}.) , >@{.

levelorder=: ;@({::L:1 _~ [: (/: #@>) <S:1@{::)

 

Required example:

 

N1=: adverb def '(<m),<y'

L=: adverb def '<m'

 

 

This tree is organized in a pre-order fashion

 

 

post-order is not that much different from pre-order, except that the children must extracted before the parent.

 

 

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

 

 

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.

 

 

 

For J novices, here's the tree instance with a few redundant parenthesis:

 

 

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.)

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:

 

 

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.

Next, let's define a few utilities:

 

 

reorder=:4 :0

parent=:3 :'parent[''data parent''=. y'

 

 

Here, <code>data</code> extracts the list of data items from the tree and <code>parent</code> extracts the structure from the tree.

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):

 

levelorder=: /:@depth@parent reorder ]

 

todo=. todo,|.ch end. end.

r

 

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.

Example use:

 

1 2 3 4 5 6 7 8 9

0 0 0 1 1 2 3 5 5

postorder dataorder example

7 4 5 2 8 9 6 3 1

 

(Once again, all we really need for this task is the first row of those results - the part that represents data.)

 

{{works with|Java|1.5+}}

 

public class TreeTraversal {

}

Output:

<pre>1 2 4 7 5 3 6 8 9

 

{{works with|Java|1.8+}}

import java.util.Queue;

import java.util.LinkedList;

System.out.println();

}

 

Output:

====Iteration====

inspired by [[#Ruby|Ruby]]

this.value = value;

this.left = left;

print("*** inorder ***"); tree.inorder(print);

print("*** postorder ***"); tree.postorder(print);

 

====Functional composition====

(for binary trees consisting of nested lists)

 

 

function preorder(n) {

return wikiTable(lstTest, true) + '\n\n' + JSON.stringify(lstTest);

 

 

Output:

|}

 

["preorder",[1,2,4,7,5,3,6,8,9]],["inorder",[7,4,2,5,1,8,6,9,3]],

 

 

 

 

'use strict';

 

}, {});

 

{{Out}}

"inorder":[7, 4, 2, 5, 1, 8, 6, 9, 3],

"postorder":[7, 4, 5, 2, 8, 9, 6, 3, 1],

 

===ES6===

{{Trans|Haskell}}

{{Trans|Python}}

"use strict";

 

// task: 'Visualize a tree'

console.log([

].join("\n"));

 

// MAIN ---

return main();

{{Out}}

preorder: 1,2,4,7,5,3,6,8,9

inorder: 7,4,2,5,1,8,6,9,3

 

The implementation assumes an array structured recursively as [ node, left, right ], where "left" and "right" may be [] or null equivalently.

if length == 0 then empty

else .[0], (.[1]|preorder), (.[2]|preorder)

 

def levelorder: [.] | recurse( tails ) | heads;

'''The task''':

# [node, left, right]

def atree: [1, [2, [4, [7,[],[]],

;

 

{{Out}}

$ jq -n -c -r -f Tree_traversal.jq

 

=={{header|Julia}}==

Any[]],

Any[]],

t = mapreduce(x -> isa(x, Number) ? (f(x); []) : x, vcat, t)

end

 

{{Out}}

=={{header|Kotlin}}==

===procedural style===

override fun toString() = "$v"

}

exec(" postOrder: ", nodes[1], ::postOrder)

exec("level-order: ", nodes[1], ::levelOrder)

 

{{Out}}

 

===object-oriented style===

data class Node(val v: Int, var left: Node? = null, var right: Node? = null) {

override fun toString() = " $v"

exec("level-order:", Node::levelOrder)

}

 

=={{header|Lambdatalk}}==

- {A.get index array} gets the value of array at index

</pre>

{def walk

 

{sort < {T}} -> 1 2 3 4 5 6 7 8 9

{sort > {T}} -> 9 8 7 6 5 4 3 2 1

 

=={{header|Lingo}}==

 

property _val, _left, _right

on getRight (me)

return me._right

 

 

on inOrder (me, node, l)

delete the last char of str

return str

 

Usage:

l = []

repeat with i = 1 to 10

put "inorder: " & trav.serialize(trav.inOrder(l[1]))

put "postorder: " & trav.serialize(trav.postOrder(l[1]))

 

{{Out}}

 

=={{header|Logo}}==

 

to node.left :node

in.order :tree [(type ? "| |)] (print)

post.order :tree [(type ? "| |)] (print)

 

=={{header|Logtalk}}==

:- object(tree_traversal).

 

 

:- end_object.

Sample output:

| ?- ?- tree_traversal::orders.

Pre-order: 1 2 4 7 5 3 6 8 9

Level-order: 1 2 3 4 5 6 7 8 9

yes

 

=={{header|Lua}}==

end

 

end

 

-- Example

 

=={{header|M2000 Interpreter}}==

A tuple is an "auto array" in M2000 Interpreter. (,) is the zero length array.

 

Module CheckIt {

Null=(,)

}

CheckIt

===Using OOP===

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.

 

Module OOP {

\\ Class is a global function (until this module end)

}

OOP

 

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)

 

Module OOP {

\\ Class is a global function (until this module end)

}

OOP

 

Using Event object as visitor

 

Module OOP {

\\ Class is a global function (until this module end)

}

OOP

 

{{out}}

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

preorder[a_[b__]] := Flatten@{a, preorder /@ {b}};

inorder[a_Integer] := a;

levelorder[a_] :=

Flatten[Table[Level[a, {n}], {n, 0, Depth@a}]] /. {b_Integer[__] :>

 

Example:

inorder[1[2[4[7], 5], 3[6[8, 9]]]]

postorder[1[2[4[7], 5], 3[6[8, 9]]]]

{{out}}

<pre>{1, 2, 4, 7, 5, 3, 6, 8, 9}

 

=={{header|Mercury}}==

:- interface.

 

print_value(V, !IO) :-

io.print(V, !IO),

Output:

<pre>preorder: 1 2 4 7 5 3 6 8 9

postorder: 7 4 5 2 8 9 6 3 1

levelorder: 1 2 3 4 5 6 7 8 9 </pre>

 

=={{header|Nim}}==

 

type

echo inorder tree

echo postorder tree

 

{{out}}

 

=={{header|Objeck}}==

 

class Test {

}

}

 

Output:

 

=={{header|OCaml}}==

| Node of 'a * 'a tree * 'a tree

 

inorder (Printf.printf "%d ") tree; print_newline ();

postorder (Printf.printf "%d ") tree; print_newline ();

Output:

<pre>1 2 4 7 5 3 6 8 9

=={{header|Oforth}}==

 

 

Tree method: initialize(v, l, r) v := v l := l r := r ;

n l dup ifNotNull: [ c send ] drop

n r dup ifNotNull: [ c send ] drop

 

{{out}}

 

=={{header|ooRexx}}==

one = .Node~new(1);

two = .Node~new(2);

nodequeue~queue(next~right)

end

Output:

<pre>

 

=={{header|Oz}}==

Tree = n(1

n(2

{Show {Inorder Tree}}

{Show {Postorder Tree}}

 

=={{header|Perl}}==

Tree nodes are represented by 3-element arrays: [0] - the value; [1] - left child; [2] - right child.

{

my $t = shift or return ();

print "in: @{[inorder($x)]}\n";

print "post: @{[postorder($x)]}\n";

Output:

<pre>pre: 1 2 4 7 5 3 6 8 9

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.

 

<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: #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>

 

{{out}}

 

=={{header|PHP}}==

private $left;

private $right;

$tree->postOrder($arr[1]);

echo "\nlevel-order:\t";

Output:

<pre>preorder: 1 2 4 7 5 3 6 8 9

 

=={{header|PicoLisp}}==

(when Node

(Fun (car Node))

(prin (align -13 (pack Order ":")))

(Order *Tree printsp)

Output:

<pre>preorder: 1 2 4 7 5 3 6 8 9

=={{header|Prolog}}==

Works with SWI-Prolog.

Tree= [1,

[2,

 

append_dl(X-Y, Y-Z, X-Z).

Output :

<pre>?- tree.

=={{header|PureBasic}}==

{{works with|PureBasic|4.5+}}

value.i

*left.node

Input()

CloseConsole()

Sample output:

<pre>preorder: 1 2 4 7 5 3 6 8 9

===Python: Procedural===

 

Node = namedtuple('Node', 'data, left, right')

print(f"{traversal.__name__:>{w}}:", end=' ')

traversal(tree)

 

'''Sample output:'''

 

Subclasses a namedtuple adding traversal methods that apply a visitor function to data at nodes of the tree in order

from sys import stdout

stdout.write('\nlevelorder: ')

tree.levelorder(printwithspace)

 

{{out}}

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.

 

 

from itertools import chain

 

if __name__ == '__main__':

{{Out}}

<pre>Tree traversals - accumulating and folding:

 

=={{header|Qi}}==

(set *tree* [1 [2 [4 [7]]

[5]]

(inorder (value *tree*))

(levelorder (value *tree*))

 

Output:

=={{header|Quackery}}==

 

 

[ ' [ 1

 

[ dup nil = iff drop done

recurse ] is pre-order ( [ --> )

 

unpack unrot

recurse

echo sp ] is post-order ( [ --> )

 

drop again

 

tree pre-order cr

tree in-order cr

tree post-order cr

 

{{out}}

7 4 2 5 1 8 6 9 3

7 4 5 2 8 9 6 3 1

 

=={{header|Racket}}==

 

#lang racket

 

(define (run order)

(printf "~a:" (object-name order))

(newline))

(for-each run (list preorder inorder postorder levelorder))

 

Output:

=={{header|Raku}}==

(formerly Perl 6)

has TreeNode $.parent;

has TreeNode $.left;

say "inorder: ",$root.in-order.join(" ");

say "postorder: ",$root.post-order.join(" ");

{{out}}

<pre>preorder: 1 2 4 7 5 3 6 8 9

postorder: 7 4 5 2 8 9 6 3 1

levelorder:1 2 3 4 5 6 7 8 9</pre>

 

=={{header|REXX}}==

/* REXX ***************************************************************

* Tree traversal

Say ''

End

{{out}}

<pre> 1

 

=={{header|Ruby}}==

def self.from_array(nested_list)

value, left, right = nested_list

root.send(mthd) {|node| print "#{node.value} "}

puts

 

{{out}}

=={{header|Rust}}==

This solution uses iteration (rather than recursion) for all traversal types.

#![feature(box_syntax, box_patterns)]

 

}

}

Output is same as Ruby et al.

 

=={{header|Scala}}==

{{works with|Scala|2.11.x}}

 

def preorder(f: IntNode => Unit) {

println(s)

}

 

Output:<pre>

levelorder: 1 2 3 4 5 6 7 8 9

</pre>

 

=={{header|SequenceL}}==

main(args(2)) :=

"preorder: " ++ toString(preOrder(testTree)) ++

)

);

{{out}}

Output:

level-order: [1,2,3,4,5,6,7,8,9]

</pre>

 

=={{header|Sidef}}==

{{trans|Perl}}

t ? [t[0], __FUNC__(t[1])..., __FUNC__(t[2])...] : [];

}

say "in: #{inorder(x)}";

say "post: #{postorder(x)}";

{{out}}

<pre>

 

'''Object subclass: EmptyNode'''

EmptyNode>>accept: aVisitor

 

EmptyNode>>traverse: aVisitorClass do: aBlock

^self accept: (aVisitorClass block: aBlock)

 

'''EmptyNode subclass: Node'''

Node>>accept: aVisitor

^aVisitor visit: self

Node class>>data: anObject

^self new data: anObject

 

'''Object subclass: Visitor'''

visit: aNode

self subclassResponsibility

Visitor class>>block: aBlock

^self new block: aBlock

 

'''Visitor subclass: InOrder'''

InOrder>>visit: aNode

aNode left accept: self.

block value: aNode.

aNode right accept: self

 

'''Visitor subclass: LevelOrder'''

LevelOrder>>visit: aNode

| queue |

add: aNode right;

yourself

 

'''Visitor subclass: PostOrder'''

PostOrder>>visit: aNode

aNode left accept: self.

aNode right accept: self.

block value: aNode

 

"Visitor subclass: PreOrder"

PreOrder>>visit: aNode

block value: aNode.

aNode left accept: self.

aNode right accept: self

 

Execute code in a Workspace:

tree := (Node data: 1)

left: ((Node data: 2)

tree traverse: LevelOrder do: [:node | Transcript print: node data; space].

Transcript cr.

 

Output in Transcript:

 

=={{header|Swift}}==

let value: T

let left: TreeNode?

print("level-order: ", terminator: "")

n.levelOrder(function: fn)

 

{{out}}

=={{header|Tcl}}==

{{works with|Tcl|8.6}} or {{libheader|TclOO}}

# Basic tree data structure stuff...

variable val l r

}

}

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:

proc Tree nested {

lassign $nested v l r

puts "postorder: [Listify $t postorder]"

puts "level-order: [Listify $t levelorder]"

Output:

<pre>preorder: 1 2 4 7 5 3 6 8 9

=={{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.

right=()

value=()

inorder 1

postorder 1

The output:

inorder: 7 4 2 5 1 8 6 9 3

postorder: 7 4 5 2 8 9 6 3 1

 

=={{header|Ursala}}==

the result on standard output as a

list of lists of naturals.

 

1^:<

#cast %nLL

 

output:

<pre>

=={{header|VBA}}==

TreeItem Class Module

Public Value As Integer

Public LeftChild As TreeItem

Public RightChild As TreeItem

Module

Dim tihead As TreeItem

 

Call LevelOrder(tihead)

End Sub

{{out}}

<pre>

level-order: 1 2 3 4 5 6 7 8 9

</pre>

 

=={{header|Wren}}==

{{trans|Kotlin}}

The object-oriented version.

construct new(v) {

_v = v

nodes[1].exec(" inOrder:", Fn.new { |n| n.inOrder() })

nodes[1].exec(" postOrder:", Fn.new { |n| n.postOrder() })

 

{{out}}

postOrder: 7 4 5 2 8 9 6 3 1

level-order: 1 2 3 4 5 6 7 8 9

</pre>

 

=={{header|zkl}}==

fcn init(val,[Node]l=Void,[Node]r=Void) { v,left,right=vm.arglist }

}

sink

}

It is easy to convert to lazy by replacing "sink.write" with "vm.yield" and wrapping the traversal with a Utils.Generator.

Node(2,

Node(4,Node(7)),

t.inOrder() .apply("v").println(" inorder");

t.postOrder() .apply("v").println(" postorder");

The "apply("v")" extracts the contents of var v from each node.

{{out}}