Tree traversal: Difference between revisions

=={{header|Draco}}==

<syntaxhighlight lang="draco">type

Node = struct {

int val;

*Node left, right;

},

Tree = *Node;

proc tree(int v; Tree l, r) Tree:

Tree t;

t := new(Node);

t*.val := v;

t*.left := l;

t*.right := r;

t

corp

proc preorder(Tree t) void:

if t /= nil then

write(t*.val, ' ');

preorder(t*.left);

preorder(t*.right)

fi

corp

proc inorder(Tree t) void:

if t /= nil then

inorder(t*.left);

write(t*.val, ' ');

inorder(t*.right)

fi

corp

proc postorder(Tree t) void:

if t /= nil then

postorder(t*.left);

postorder(t*.right);

write(t*.val, ' ')

fi

corp

proc levelorder(Tree t) void:

[256]Tree q;

word s, e;

s := 0;

q[s] := t;

e := 1;

while s /= e do

if q[s] /= nil then

q[e] := q[s]*.left;

q[e+1] := q[s]*.right;

e := e+2;

write(q[s]*.val, ' ')

fi;

s := s+1

od

corp

proc main() void:

Tree t;

t := tree(1,

tree(2,

tree(4,

tree(7,nil,nil),

nil),

tree(5,nil,nil)),

tree(3,

tree(6,

tree(8,nil,nil),

tree(9,nil,nil)),

nil));

write("preorder: "); preorder(t); writeln();

write("inorder: "); inorder(t); writeln();

write("postorder: "); postorder(t); writeln();

write("level-order: "); levelorder(t); writeln();

corp</syntaxhighlight>

{{out}}

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

inorder: 7 4 2 5 1 8 6 9 3

postorder: 7 4 5 2 8 9 6 3 1

level-order: 1 2 3 4 5 6 7 8 9</pre>