(original) (raw)

#!/usr/bin/env setl -- -- Tree traversal in SETL. -- -- From http://rosettacode.org/wiki/Tree\_traversal -- """ -- You are encouraged to solve this task according to the task -- description, using any language you may know. -- -- Implement a binary tree where each node carries an integer, -- and implement preoder, inorder, postorder and level-order traversal. -- Use those traversals to output the following tree: -- -- 1 -- / \ -- / \ -- / \ -- 2 3 -- / \ / -- 4 5 6 -- / / \ -- 7 8 9 -- -- The correct output should look like this: -- -- 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 -- """ -- -- Also see http://en.wikipedia.org/wiki/Tree\_traversal -- -- -- This SETL program was created by Hakan Kjellerstrand (hakank@bonetmail.com) -- Also see my SETL page: http://www.hakank.org/setl/ -- tree := [1, [2, [4, [7]], [5]], [3, [6, [8], [9]]]]; print("preorder :", preorder(tree)); print("inorder :", inorder(tree)); print("postorder :", postorder(tree)); print("levelorder:", levelorder(tree)); -- preorder procedure preorder(L); return case when L = om => [] otherwise => [L(1)] + preorder(L(2)) + preorder(L(3)) end case; end procedure; -- inorder procedure inorder(L); return case when L = om => [] otherwise => inorder(L(2)) + [L(1)] + inorder(L(3)) end case; end procedure; -- postorder procedure postorder(L); return case when L = om => [] otherwise => postorder(L(2)) + postorder(L(3)) + [L(1)] end case; end procedure; -- leverlorder procedure levelorder(L); q := [L]; res := []; while q /= [] loop n fromb q; res with:= n(1); q with:= n(2); q with:= n(3); end loop; return res; end procedure;