31 lines
901 B
Text
31 lines
901 B
Text
class Node{ var [mixin=Node]left,right; var v;
|
|
fcn init(val,[Node]l=Void,[Node]r=Void) { v,left,right=vm.arglist }
|
|
}
|
|
|
|
class BTree{ var [mixin=Node] root;
|
|
fcn init(r){ root=r }
|
|
const VISIT=Void, LEFT="left", RIGHT="right";
|
|
fcn preOrder { traverse(VISIT,LEFT, RIGHT) }
|
|
fcn inOrder { traverse(LEFT, VISIT,RIGHT) }
|
|
fcn postOrder { traverse(LEFT, RIGHT,VISIT) }
|
|
fcn [private] traverse(order){ //--> list of Nodes
|
|
sink:=List();
|
|
fcn(sink,[Node]n,order){
|
|
if(n){ foreach o in (order){
|
|
if(VISIT==o) sink.write(n);
|
|
else self.fcn(sink,n.setVar(o),order); // actually get var, eg n.left
|
|
}}
|
|
}(sink,root,vm.arglist);
|
|
sink
|
|
}
|
|
fcn levelOrder{ // breadth first
|
|
sink:=List(); q:=List(root);
|
|
while(q){
|
|
n:=q.pop(0); l:=n.left; r:=n.right;
|
|
sink.write(n);
|
|
if(l) q.append(l);
|
|
if(r) q.append(r);
|
|
}
|
|
sink
|
|
}
|
|
}
|