For parts (b)–(e), use array indices as tree handles. This also makes the shared storage in part (d) type-correct: both pending handles and output markers occupy integer cells. Zero denotes a leaf of a rooted tree; a positive handle denotes a fork whose children are in Initialize
nodes[t-1]. Only finite acyclic structures are admitted. An allocated fork's children are themselves valid handles.CONST MaxForks = 100000;
TYPE Tree = INTEGER;
Node = RECORD left, right: Tree END;
Arena = ARRAY MaxForks OF Node;
VAR nodes: Arena;
used: INTEGER;
PROCEDURE NewFork(left, right: Tree): Tree;
BEGIN
ASSERT(used < MaxForks);
nodes[used].left := left; nodes[used].right := right;
INC(used);
RETURN used
END NewFork;
PROCEDURE Preorder(t: Tree; VAR out: ARRAY OF INTEGER;
VAR count: INTEGER);
PROCEDURE Visit(p: Tree);
BEGIN
IF p = 0 THEN
out[count] := 0; INC(count)
ELSE
out[count] := 1; INC(count);
Visit(nodes[p-1].left); Visit(nodes[p-1].right)
END
END Visit;
BEGIN
count := 0; Visit(t)
END Preorder;used := 0 before constructing any trees; NewFork allocates within this arena. The fixed capacity is an implementation parameter and may be replaced by a dynamically allocated arena. The returned prefix out[0..count) encodes Boolean values by and . This encoding is part of the chosen representation, not a conversion of a pointer into a Boolean value.The recursion invariant is that
Visit(p) appends exactly the preorder traversal of the subtree represented by p. If the full binary tree has forks, it has leaves; henceEach occurrence is visited once, using linear time complexity and a call stack bounded by the height of a binary tree. The arena is the input representation, not an extra copy made by the traversal. Articles by others on the same topic
There are currently no matching articles.