51 lines
1.3 KiB
Text
51 lines
1.3 KiB
Text
-- parent script "BinaryTreeTraversal"
|
|
|
|
on inOrder (me, node, l)
|
|
if voidP(l) then l = []
|
|
if voidP(node) then return l
|
|
if not voidP(node.getLeft()) then l = me.inOrder(node.getLeft(), l)
|
|
l.add(node)
|
|
if not voidP(node.getRight()) then l = me.inOrder(node.getRight(), l)
|
|
return l
|
|
end
|
|
|
|
on preOrder (me, node, l)
|
|
if voidP(l) then l = []
|
|
if voidP(node) then return l
|
|
l.add(node)
|
|
if not voidP(node.getLeft()) then l = me.preOrder(node.getLeft(), l)
|
|
if not voidP(node.getRight()) then l = me.preOrder(node.getRight(), l)
|
|
return l
|
|
end
|
|
|
|
on postOrder (me, node, l)
|
|
if voidP(l) then l = []
|
|
if voidP(node) then return l
|
|
if not voidP(node.getLeft()) then l = me.postOrder(node.getLeft(), l)
|
|
if not voidP(node.getRight()) then l = me.postOrder(node.getRight(), l)
|
|
l.add(node)
|
|
return l
|
|
end
|
|
|
|
on levelOrder (me, node)
|
|
l = []
|
|
queue = [node]
|
|
repeat while queue.count
|
|
node = queue[1]
|
|
queue.deleteAt(1)
|
|
l.add(node)
|
|
if not voidP(node.getLeft()) then queue.add(node.getLeft())
|
|
if not voidP(node.getRight()) then queue.add(node.getRight())
|
|
end repeat
|
|
return l
|
|
end
|
|
|
|
-- print utility function
|
|
on serialize (me, l)
|
|
str = ""
|
|
repeat with node in l
|
|
put node.getValue()&" " after str
|
|
end repeat
|
|
delete the last char of str
|
|
return str
|
|
end
|