4.3BSD/usr/contrib/icon/port/btrees.icn

#
#          B I N A R Y   T R E E S
#

#  This program accepts string representations of binary trees from
#  standard input.  It performs a tree walk and lists the leaves of
#  each tree.

record node(data,ltree,rtree)

procedure main()
   local line, tree
   while line := read() do {
      tree := tform(line)
      write("tree walk")
      every write(walk(tree))
      write("leaves")
      every write(leaves(tree))
      }
end

procedure tform(s)
   local value,left,right
   if /s then return
   s ? if value := tab(upto('(')) then {
      move(1)
      left := tab(bal(','))
      move(1)
      right := tab(bal(')'))
      return node(value,tform(left),tform(right))
      }
      else return node(s)
end

procedure walk(t)
   suspend walk(\t.ltree | \t.rtree)
   return t.data
end

procedure leaves(t)
   if not(\t.ltree | \t.rtree) then return t.data
   suspend leaves(\t.ltree | \t.rtree)
end