Tree traversal: Difference between revisions

Line 34:

<syntaxhighlight lang=11l>T Node

<syntaxhighlight lang="11l">T Node

Int data

Node? left

Line 117:

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

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program deftree64.s */

Line 508:

=={{header|ACL2}}==

<syntaxhighlight lang=lisp>(defun flatten-preorder (tree)

<syntaxhighlight lang="lisp">(defun flatten-preorder (tree)

(if (endp tree)

nil

Line 560:

The user must type in the monitor the following command after compilation and before running the program!<pre>SET EndProg=*</pre>

<syntaxhighlight lang=~~Action~~!>CARD EndProg ;required for ALLOCATE.ACT

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

Line 821:

=={{header|Ada}}==

<syntaxhighlight lang=~~Ada~~>with Ada.Text_Io; use Ada.Text_Io;

<syntaxhighlight lang="ada">with Ada.Text_Io; use Ada.Text_Io;

with Ada.Unchecked_Deallocation;

with Ada.Containers.Doubly_Linked_Lists;

Line 931:

=={{header|Agda}}==

<syntaxhighlight lang=~~Agda~~>open import Data.List using (List; _?_; []; concat)

<syntaxhighlight lang="agda">open import Data.List using (List; _?_; []; concat)

open import Data.Nat using (N; suc; zero)

open import Level using (Level)

Line 1,017:

<syntaxhighlight lang=algol68>MODE VALUE = INT;

<syntaxhighlight lang="algol68">MODE VALUE = INT;

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

Line 1,152:

Written in Dyalog APL with dfns.

<syntaxhighlight lang=~~APL~~>preorder ? {l r?? ?? ? ? (?r)???(×?r)?(?l)???(×?l)?? ?? ?}

<syntaxhighlight lang="apl">preorder ? {l r?? ?? ? ? (?r)???(×?r)?(?l)???(×?l)?? ?? ?}

inorder ? {l r?? ?? ? ? (?r)???(×?r)?? ???(?l)???(×?l)??}

postorder? {l r?? ?? ? ? ? ???(?r)???(×?r)?(?l)???(×?l)??}

Line 1,174:

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

<syntaxhighlight lang="apl">tree?1(2(4(7??)?)(5??))(3(6(8??)(9??))?)

visit?{?,(×??)???}

children?{?¨@(×°?¨)1??}</syntaxhighlight>

Line 1,198:

=={{header|AppleScript}}==

{{Trans|JavaScript}}(ES6)

<syntaxhighlight lang=~~AppleScript~~>on run

<syntaxhighlight lang="applescript">on run

-- Sample tree of integers

set tree to node(1, ¬

Line 1,538:

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

/* ARM assembly Raspberry PI */

Line 2,022:

=={{header|ATS}}==

<syntaxhighlight lang=~~ATS~~>#include

<syntaxhighlight lang="ats">#include

"share/atspre_staload.hats"

//

Line 2,129:

=={{header|AutoHotkey}}==

<syntaxhighlight lang=~~AutoHotkey~~>AddNode(Tree,1,2,3,1) ; Build global Tree

<syntaxhighlight lang="autohotkey">AddNode(Tree,1,2,3,1) ; Build global Tree

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

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

Line 2,184:

=={{header|AWK}}==

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

if (node == "")

Line 2,277:

=={{header|Bracmat}}==

<syntaxhighlight lang=bracmat>(

<syntaxhighlight lang="bracmat">(

( tree

= 1

Line 2,320:

=={{header|C}}==

<syntaxhighlight lang=c>#include <stdlib.h>

<syntaxhighlight lang="c">#include <stdlib.h>

#include <stdio.h>

Line 2,468:

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

<syntaxhighlight lang=csharp>using System;

<syntaxhighlight lang="csharp">using System;

using System.Collections.Generic;

using System.Linq;

Line 2,546:

<syntaxhighlight lang=cpp>#include <boost/scoped_ptr.hpp>

<syntaxhighlight lang="cpp">#include <boost/scoped_ptr.hpp>

#include <iostream>

#include <queue>

Line 2,642:

===Array version===

<syntaxhighlight lang=cpp>#include <iostream>

<syntaxhighlight lang="cpp">#include <iostream>

using namespace std;

Line 2,714:

===Modern C++===

<syntaxhighlight lang=cpp>#include <iostream>

<syntaxhighlight lang="cpp">#include <iostream>

#include <memory>

#include <queue>

Line 2,819:

=={{header|Ceylon}}==

<syntaxhighlight lang=ceylon>import ceylon.collection {

<syntaxhighlight lang="ceylon">import ceylon.collection {

ArrayList

}

Line 2,918:

=={{header|Clojure}}==

<syntaxhighlight lang=clojure>(defn walk [node f order]

<syntaxhighlight lang="clojure">(defn walk [node f order]

(when node

(doseq [o order]

Line 2,964:

=={{header|CLU}}==

<syntaxhighlight lang=clu>bintree = cluster [T: type] is leaf, node,

<syntaxhighlight lang="clu">bintree = cluster [T: type] is leaf, node,

pre_order, post_order, in_order, level_order

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

Line 3,065:

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

Line 3,124:

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

<syntaxhighlight lang=lisp>(defun preorder (node f)

<syntaxhighlight lang="lisp">(defun preorder (node f)

(when node

(funcall f (first node))

Line 3,172:

=={{header|Coq}}==

<syntaxhighlight lang=coq>Require Import Utf8.

<syntaxhighlight lang="coq">Require Import Utf8.

Require Import List.

Line 3,227:

=={{header|Crystal}}==

class Node(T)

property left : Nil | Node(T)

Line 3,320:

=={{header|D}}==

This code is long because it's very generic.

<syntaxhighlight lang=d>import std.stdio, std.traits;

<syntaxhighlight lang="d">import std.stdio, std.traits;

const final class Node(T) {

Line 3,406:

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

<syntaxhighlight lang=d>const struct Node(T) {

<syntaxhighlight lang="d">const struct Node(T) {

T v;

Node* l, r;

Line 3,458:

===Alternative Lazy Version===

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

<syntaxhighlight lang=d>import std.stdio, std.algorithm, std.range, std.string;

<syntaxhighlight lang="d">import std.stdio, std.algorithm, std.range, std.string;

const struct Tree(T) {

Line 3,530:

=={{header|E}}==

<syntaxhighlight lang=e>def btree := [1, [2, [4, [7, null, null],

<syntaxhighlight lang="e">def btree := [1, [2, [4, [7, null, null],

null],

[5, null, null]],

Line 3,582:

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

<syntaxhighlight lang=eiffel >note

<syntaxhighlight lang="eiffel ">note

description : "Application for tree traversal demonstration"

output : "[

Line 3,633:

end -- class APPLICATION</syntaxhighlight>

<syntaxhighlight lang=eiffel >note

<syntaxhighlight lang="eiffel ">note

description : "A simple node for a binary tree"

libraries : "Relies on LINKED_LIST from EiffelBase"

Line 3,763:

=={{header|Elena}}==

ELENA 5.0 :

<syntaxhighlight lang=elena>import extensions;

<syntaxhighlight lang="elena">import extensions;

import extensions'routines;

import system'collections;

Line 3,894:

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

Line 3,933:

</syntaxhighlight>

Tests

use BinaryTreeTraversals (Tree, integer);

Line 3,957:

=={{header|Elixir}}==

<syntaxhighlight lang=elixir>defmodule Tree_Traversal do

<syntaxhighlight lang="elixir">defmodule Tree_Traversal do

defp tnode, do: {}

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

Line 4,023:

=={{header|Erlang}}==

<syntaxhighlight lang=erlang>-module(tree_traversal).

<syntaxhighlight lang="erlang">-module(tree_traversal).

-export([main/0]).

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

Line 4,074:

=={{header|Euphoria}}==

<syntaxhighlight lang=euphoria>constant VALUE = 1, LEFT = 2, RIGHT = 3

<syntaxhighlight lang="euphoria">constant VALUE = 1, LEFT = 2, RIGHT = 3

constant tree = {1,

Line 4,149:

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

<syntaxhighlight lang=fsharp>open System

<syntaxhighlight lang="fsharp">open System

open System.IO

Line 4,226:

=={{header|Factor}}==

<syntaxhighlight lang=factor>USING: accessors combinators deques dlists fry io kernel

<syntaxhighlight lang="factor">USING: accessors combinators deques dlists fry io kernel

math.parser ;

IN: rosetta.tree-traversal

Line 4,300:

=={{header|Fantom}}==

class Tree

{

Line 4,381:

=={{header|Forth}}==

<syntaxhighlight lang=forth>\ binary tree (dictionary)

<syntaxhighlight lang="forth">\ binary tree (dictionary)

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

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

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.

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

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 (LINKL(HAS).GT.0) CALL TARZAN(LINKL(HAS),STYLE)

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.

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

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

CALL TARZAN(1,HOW)

Line 4,465:

===Source===

MODULE ARAUCARIA !Cunning crosswords, also.

INTEGER ENUFF !To suit the set example.

Line 4,687:

=={{header|FreeBASIC}}==

#define NULL 0

Line 4,772:

=={{header|FunL}}==

<syntaxhighlight lang=funl>data Tree = Empty | Node( value, left, right )

<syntaxhighlight lang="funl">data Tree = Empty | Node( value, left, right )

def

Line 4,951:

This is like many examples on this page.

<syntaxhighlight lang=go>package main

<syntaxhighlight lang="go">package main

import "fmt"

Line 5,046:

===Flat slice===

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

<syntaxhighlight lang=go>package main

<syntaxhighlight lang="go">package main

import "fmt"

Line 5,120:

=={{header|Groovy}}==

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

<syntaxhighlight lang=groovy>def preorder;

<syntaxhighlight lang="groovy">def preorder;

preorder = { Node node ->

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

Line 5,157:

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

<syntaxhighlight lang=groovy>try {

<syntaxhighlight lang="groovy">try {

new BinaryNodeBuilder().'1' {

a {}

Line 5,169:

Test case #1 (from the task definition)

<syntaxhighlight lang=groovy>// 1

<syntaxhighlight lang="groovy">// 1

// / \

// 2 3

Line 5,188:

Test case #2 (tests single right child)

<syntaxhighlight lang=groovy>// 1

<syntaxhighlight lang="groovy">// 1

// / \

// 2 3

Line 5,207:

Run tests:

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

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

Line 5,242:

=={{header|Haskell}}==

===Left Right nodes===

<syntaxhighlight lang=haskell>---------------------- TREE TRAVERSAL --------------------

<syntaxhighlight lang="haskell">---------------------- TREE TRAVERSAL --------------------

data Tree a

Line 5,332:

<syntaxhighlight lang=haskell>import Data.Bool (bool)

<syntaxhighlight lang="haskell">import Data.Bool (bool)

import Data.Tree (Tree (..), drawForest, drawTree, foldTree)

Line 5,452:

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

<syntaxhighlight lang=~~Icon~~>procedure main()

<syntaxhighlight lang="icon">procedure main()

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

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

Line 5,495:

=={{header|Isabelle}}==

<syntaxhighlight lang=~~Isabelle~~>theory Tree

<syntaxhighlight lang="isabelle">theory Tree

imports Main

begin

Line 5,577:

=={{header|J}}==

<syntaxhighlight lang=J>preorder=: ]S:0

<syntaxhighlight lang="j">preorder=: ]S:0

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

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

Line 5,584:

Required example:

<syntaxhighlight lang=J>N2=: conjunction def '(<m),(<n),<y'

<syntaxhighlight lang="j">N2=: conjunction def '(<m),(<n),<y'

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

L=: adverb def '<m'

Line 5,592:

This tree is organized in a pre-order fashion

<syntaxhighlight lang=J> preorder tree

<syntaxhighlight lang="j"> preorder tree

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.

<syntaxhighlight lang=J> postorder tree

<syntaxhighlight lang="j"> postorder tree

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

<syntaxhighlight lang=J> inorder tree

<syntaxhighlight lang="j"> inorder tree

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.

<syntaxhighlight lang=J> levelorder tree

<syntaxhighlight lang="j"> levelorder tree

1 2 3 4 5 6 7 8 9</syntaxhighlight>

Line 5,613:

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

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:

<syntaxhighlight lang=J>example=:1 8 3 4 7 5 9 6 2,: 0 7 0 8 3 8 7 2 0</syntaxhighlight>

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

Line 5,627:

Next, let's define a few utilities:

<syntaxhighlight lang=J>depth=: +/@((~: , (~: i.@#@{.)~) {:@,)@({~^:a:)

<syntaxhighlight lang="j">depth=: +/@((~: , (~: i.@#@{.)~) {:@,)@({~^:a:)

reorder=:4 :0

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

<syntaxhighlight lang=J>dataorder=: /:@data reorder ]

<syntaxhighlight lang="j">dataorder=: /:@data reorder ]

levelorder=: /:@depth@parent reorder ]

Line 5,709:

Example use:

<syntaxhighlight lang=J> levelorder dataorder example

<syntaxhighlight lang="j"> levelorder dataorder example

1 2 3 4 5 6 7 8 9

0 0 0 1 1 2 3 5 5

Line 5,732:

<syntaxhighlight lang=java5>import java.util.*;

<syntaxhighlight lang="java5">import java.util.*;

public class TreeTraversal {

Line 5,833:

<syntaxhighlight lang=java5>import java.util.function.Consumer;

<syntaxhighlight lang="java5">import java.util.function.Consumer;

import java.util.Queue;

import java.util.LinkedList;

Line 5,970:

====Iteration====

inspired by [[#Ruby|Ruby]]

<syntaxhighlight lang=javascript>function BinaryTree(value, left, right) {

<syntaxhighlight lang="javascript">function BinaryTree(value, left, right) {

this.value = value;

this.left = left;

Line 6,015:

(for binary trees consisting of nested lists)

<syntaxhighlight lang=javascript>(function () {

<syntaxhighlight lang="javascript">(function () {

function preorder(n) {

Line 6,120:

|}

<syntaxhighlight lang=~~JavaScript~~>[["Traversal","Nodes visited"],

<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]],

["postorder",[7,4,5,2,8,9,6,3,1]],["levelorder",[1,2,3,4,5,6,7,8,9]]]</syntaxhighlight>

Line 6,132:

<syntaxhighlight lang=~~JavaScript~~>(function () {

<syntaxhighlight lang="javascript">(function () {

'use strict';

Line 6,254:

})();</syntaxhighlight>

<syntaxhighlight lang=~~JavaScript~~>{"preorder":[1, 2, 4, 7, 5, 3, 6, 8, 9],

<syntaxhighlight lang="javascript">{"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],

Line 6,263:

<syntaxhighlight lang=~~JavaScript~~>(() => {

<syntaxhighlight lang="javascript">(() => {

"use strict";

Line 6,408:

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:

<syntaxhighlight lang="jq">def preorder:

if length == 0 then empty

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

Line 6,436:

</syntaxhighlight>

'''The task''':

<syntaxhighlight lang=jq>def task:

<syntaxhighlight lang="jq">def task:

# [node, left, right]

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

Line 6,461:

=={{header|Julia}}==

<syntaxhighlight lang=~~Julia~~>tree = Any[1, Any[2, Any[4, Any[7, Any[],

<syntaxhighlight lang="julia">tree = Any[1, Any[2, Any[4, Any[7, Any[],

Any[]],

Line 6,502:

=={{header|Kotlin}}==

===procedural style===

<syntaxhighlight lang=scala>data class Node(val v: Int, var left: Node? = null, var right: Node? = null) {

<syntaxhighlight lang="scala">data class Node(val v: Int, var left: Node? = null, var right: Node? = null) {

override fun toString() = "$v"

}

Line 6,579:

===object-oriented style===

<syntaxhighlight lang=scala>fun main(args: Array<String>) {

<syntaxhighlight lang="scala">fun main(args: Array<String>) {

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

override fun toString() = " $v"

Line 6,633:

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

</pre>

{def walk

Line 6,671:

=={{header|Lingo}}==

<syntaxhighlight lang=lingo>-- parent script "BinaryTreeNode"

<syntaxhighlight lang="lingo">-- parent script "BinaryTreeNode"

property _val, _left, _right

Line 6,700:

end</syntaxhighlight>

<syntaxhighlight lang=lingo>-- parent script "BinaryTreeTraversal"

<syntaxhighlight lang="lingo">-- parent script "BinaryTreeTraversal"

on inOrder (me, node, l)

Line 6,753:

Usage:

<syntaxhighlight lang=lingo>-- create the tree

<syntaxhighlight lang="lingo">-- create the tree

l = []

repeat with i = 1 to 10

Line 6,783:

=={{header|Logo}}==

<syntaxhighlight lang=logo>; nodes are [data left right], use "first" to get data

<syntaxhighlight lang="logo">; nodes are [data left right], use "first" to get data

to node.left :node

Line 6,842:

=={{header|Logtalk}}==

:- object(tree_traversal).

Line 6,925:

</syntaxhighlight>

Sample output:

| ?- ?- tree_traversal::orders.

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

Line 6,935:

=={{header|Lua}}==

<syntaxhighlight lang=~~Lua~~>-- Utility

<syntaxhighlight lang="lua">-- Utility

local function append(t1, t2)

for _, v in ipairs(t2) do

Line 6,986:

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

Module CheckIt {

Null=(,)

Line 7,051:

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)

Line 7,140:

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)

Line 7,231:

Using Event object as visitor

Module OOP {

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

Line 7,333:

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

<syntaxhighlight lang=mathematica>preorder[a_Integer] := a;

<syntaxhighlight lang="mathematica">preorder[a_Integer] := a;

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

inorder[a_Integer] := a;

Line 7,344:

Example:

<syntaxhighlight lang=mathematica>preorder[1[2[4[7], 5], 3[6[8, 9]]]]

<syntaxhighlight lang="mathematica">preorder[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]]]]

Line 7,355:

=={{header|Mercury}}==

<syntaxhighlight lang=mercury>:- module tree_traversal.

<syntaxhighlight lang="mercury">:- module tree_traversal.

:- interface.

Line 7,455:

=={{header|Nim}}==

<syntaxhighlight lang=nim>import deques

<syntaxhighlight lang="nim">import deques

type

Line 7,508:

=={{header|Objeck}}==

??use Collection;

Line 7,632:

=={{header|OCaml}}==

<syntaxhighlight lang=ocaml>type 'a tree = Empty

<syntaxhighlight lang="ocaml">type 'a tree = Empty

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

Line 7,690:

=={{header|Oforth}}==

<syntaxhighlight lang=~~Oforth~~>Object Class new: Tree(v, l, r)

<syntaxhighlight lang="oforth">Object Class new: Tree(v, l, r)

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

Line 7,743:

=={{header|ooRexx}}==

one = .Node~new(1);

two = .Node~new(2);

Line 7,837:

=={{header|Oz}}==

<syntaxhighlight lang=oz>declare

<syntaxhighlight lang="oz">declare

Tree = n(1

n(2

Line 7,898:

=={{header|Perl}}==

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

<syntaxhighlight lang=perl>sub preorder

<syntaxhighlight lang="perl">sub preorder

{

my $t = shift or return ();

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.

constant VALUE = 1, LEFT = 2, RIGHT = 3

Line 8,003:

=={{header|PHP}}==

<syntaxhighlight lang=~~PHP~~>class Node {

<syntaxhighlight lang="php">class Node {

private $left;

private $right;

Line 8,112:

=={{header|PicoLisp}}==

<syntaxhighlight lang=~~PicoLisp~~>(de preorder (Node Fun)

<syntaxhighlight lang="picolisp">(de preorder (Node Fun)

(when Node

(Fun (car Node))

Line 8,154:

=={{header|Prolog}}==

Works with SWI-Prolog.

<syntaxhighlight lang=~~Prolog~~>tree :-

<syntaxhighlight lang="prolog">tree :-

Tree= [1,

[2,

Line 8,222:

=={{header|PureBasic}}==

<syntaxhighlight lang=~~PureBasic~~>Structure node

<syntaxhighlight lang="purebasic">Structure node

value.i

*left.node

Line 8,367:

===Python: Procedural===

<syntaxhighlight lang=python>from collections import namedtuple

<syntaxhighlight lang="python">from collections import namedtuple

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

Line 8,454:

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

<syntaxhighlight lang="python">from collections import namedtuple

from sys import stdout

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.

<syntaxhighlight lang=python>'''Tree traversals'''

<syntaxhighlight lang="python">'''Tree traversals'''

from itertools import chain

Line 8,758:

=={{header|Qi}}==

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

[5]]

Line 8,815:

Requires the words at [[Queue/Definition#Quackery]] for <code>level-order</code>.

<syntaxhighlight lang=~~Quackery~~> [ this ] is nil ( --> [ )

<syntaxhighlight lang="quackery"> [ this ] is nil ( --> [ )

[ ' [ 1

Line 8,872:

=={{header|Racket}}==

#lang racket

Line 8,910:

=={{header|Raku}}==

(formerly Perl 6)

<syntaxhighlight lang=~~perl6~~>class TreeNode {

<syntaxhighlight lang="raku" line>class TreeNode {

has TreeNode $.parent;

has TreeNode $.left;

Line 8,975:

=={{header|REBOL}}==

tree: [1 [2 [4 [7 [] []] []] [5 [] []]] [3 [6 [8 [] []] [9 [] []]] []]]

; "compacted" version

Line 9,032:

=={{header|REXX}}==

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

* Tree traversal

Line 9,366:

=={{header|Ruby}}==

<syntaxhighlight lang=ruby>BinaryTreeNode = Struct.new(:value, :left, :right) do

<syntaxhighlight lang="ruby">BinaryTreeNode = Struct.new(:value, :left, :right) do

def self.from_array(nested_list)

value, left, right = nested_list

Line 9,416:

=={{header|Rust}}==

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

#![feature(box_syntax, box_patterns)]

Line 9,597:

=={{header|Scala}}==

<syntaxhighlight lang=~~Scala~~>case class IntNode(value: Int, left: Option[IntNode] = None, right: Option[IntNode] = None) {

<syntaxhighlight lang="scala">case class IntNode(value: Int, left: Option[IntNode] = None, right: Option[IntNode] = None) {

def preorder(f: IntNode => Unit) {

Line 9,661:

=={{header|Scheme}}==

<syntaxhighlight lang=scheme>(define (preorder tree)

<syntaxhighlight lang="scheme">(define (preorder tree)

(if (null? tree)

'()

Line 9,734:

=={{header|SequenceL}}==

main(args(2)) :=

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

Line 9,789:

=={{header|Sidef}}==

<syntaxhighlight lang=ruby>func preorder(t) {

<syntaxhighlight lang="ruby">func preorder(t) {

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

}

Line 9,835:

'''Object subclass: EmptyNode'''