Wednesday, December 29, 2010

CSE 202 Pseudo Codes 1



Iterative Tree Traversal


There are three types of tree traversals, namely, inorder, preorder and postorder. For some strange reasons, students @CSE-DU are forced to write iterative versions of these. I am just noting it down here again.

The Node is composed of three fields, namely, Info (data for this node), Left (pointer to left child), Right (pointer to right child). The pseudo-codes are shown below

Preorder



Preorder ( Info, Left, Right, root )
top := 1, Stack[top] := NULL, ptr := root;
repeat while ptr != NULL
apply process() to Info[ptr];
if Right[ptr] != NULL then
top := top + 1, Stack[top] = Right[ptr];
if Left[ptr] != NULL then
ptr = Left[ptr];
else
ptr = Stack[top], top := top - 1;
exit

Inorder



Inorder ( Info, Left, Right, root )
top := 1, Stack[top] := NULL, ptr := root;
repeat while ptr != NULL
top := top + 1, Stack[top] = ptr, ptr = Left[ptr];
ptr = Stack[top], top := top - 1;
repeat while ptr != NULL
apply process() to Info[ptr];
if Right[ptr] != NULL then
ptr := Right[ptr];
go to step 03;
ptr := Stack[top], top := top - 1;
exit

Postorder



Postorder ( Info, Left, Right, root )
top := 1, Stack[top] := NULL, ptr := root;
repeat while ptr != NULL
top := top + 1, Stack[top] = ptr, ptr = Left[ptr];
repeat while Stack[top] != NULL and ptr = Right[Stack[top]]
ptr := Stack[top], top := top - 1;
apply process() to Info[ptr];
if Stack[top] != NULL then
ptr := Right[Stack[top]];
go to step 03;
exit

Really pointless though!

1 comment: