Tree traversal: Difference between revisions

</pre>

=={{header|XPL0}}==

<syntaxhighlight lang "XPL0">def \Node\ Left, Data, Right;

proc PreOrder(Node); \Traverse tree at Node in preorder

int Node;

[if Node # 0 then

[IntOut(0, Node(Data)); ChOut(0, ^ );

PreOrder(Node(Left));

PreOrder(Node(Right));

];

];

proc InOrder(Node); \Traverse tree at Node in inorder

int Node;

[if Node # 0 then

[InOrder(Node(Left));

IntOut(0, Node(Data)); ChOut(0, ^ );

InOrder(Node(Right));

];

];

proc PostOrder(Node); \Traverse tree at Node in postorder

int Node;

[if Node # 0 then

[PostOrder(Node(Left));

PostOrder(Node(Right));

IntOut(0, Node(Data)); ChOut(0, ^ );

];

];

proc LevelOrder(Node); \Traverse tree at Node in level-order

int Node;

def S=100*3; \size of queue (must be a multiple of 3 for wrap-around)

int Q(S), \queue (FIFO)

F, E; \fill and empty indexes

proc EnQ(Node); \Enqueue Node

int Node;

[Q(F):= Node(Left); F:= F+1;

Q(F):= Node(Data); F:= F+1;

Q(F):= Node(Right); F:= F+1;

if F >= S then F:= 0;

];

proc DeQ; \Dequeue Node

[Node(Left):= Q(E); E:= E+1;

Node(Data):= Q(E); E:= E+1;

Node(Right):= Q(E); E:= E+1;

if E >= S then E:= 0;

];

[F:= 0; E:= 0; \empty queue

EnQ(Node);

while E # F do

[DeQ;

IntOut(0, Node(Data)); ChOut(0, ^ );

if Node(Left) # 0 then

EnQ(Node(Left));

if Node(Right) # 0 then

EnQ(Node(Right));

];

];

int Tree;

[Tree:= [[ [[0,7,0],4,0], 2, [0,5,0]], 1, [ [[0,8,0], 6, [0,9,0]], 3, 0 ]];

Text(0, "preorder: "); PreOrder(Tree); CrLf(0);

Text(0, "inorder: "); InOrder(Tree); CrLf(0);

Text(0, "postorder: "); PostOrder(Tree); CrLf(0);

Text(0, "level-order: "); LevelOrder(Tree); CrLf(0);

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