binary tree drawing
Click reload to regenerate
bug found (rightmost, leftmost impl.)
bug fixed... maybe?
it seems working correctly
but not so much tight
/**
* Copyright wrotenodoc ( http://wonderfl.net/user/wrotenodoc )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/e3O1
*/
package {
import flash.display.Sprite;
import flash.display.Graphics
import flash.text.TextField
public class FlashTest extends Sprite {
private var canv:Sprite
private var tree:Tree
private const size:Number = 5
private const spaceX:Number = 15
private const spaceY:Number = 15
private var _tf:TextField = new TextField
public function FlashTest() {
// write as3 code here..
canv = new Sprite
tree = new Tree
addChild(canv)
canv.x = stage.stageWidth / 2
canv.y = 50
addChild(_tf)
_tf.autoSize = "left"
build(tree, 0)
process(tree)
adjustRoot(tree)
render(canv.graphics, tree)
stage.addEventListener("mouseMove", function(e:Object):void {
canv.scaleX = 0.1 + 0.9 * (mouseX / stage.stageWidth)
})
}
private function build(T:Tree, level:int):void {
var prob:Number = 1 / (1 + level*0.1)
if(Math.random() < prob){
T.left = new Tree
T.left.parent = T
build(T.left, level+1)
}
if(Math.random() < prob){
T.right = new Tree
T.right.parent = T
build(T.right, level+4)
}
}
public function render(g:Graphics, T:Tree):void {
var level:int = 0
var queue:Array = [T]
var num:int
while(queue.length){
num = queue.length
while(num--){
T = queue.shift()
g.beginFill(0x123456, 0.5)
g.drawCircle(T.x * spaceX, level * spaceY, size)
g.endFill()
if(T.parent){
g.lineStyle(1, T.parent.left==T ? 0xff0000 : 0x0000ff)
g.moveTo(T.x * spaceX, level * spaceY)
g.lineTo(T.parent.x * spaceX, (level-1)*spaceY)
g.lineStyle()
}
if(T.left) queue.push(T.left)
if(T.right) queue.push(T.right)
}
level++
}
}
public function process(T:Tree):void {
if(T == null) return
process(T.left)
process(T.right)
if(T.left == null && T.right == null){
// no children
T.x = 0
}else if(T.right == null){
// has left child only
T.x = T.left.x + 1
}else if(T.left == null){
// has right child only
T.x = T.right.x - 1
}else{
// has both
// BUG: lx, rx are calculated incorrectly
var lx:int = T.left.rightmost.x
var rx:int = T.right.leftmost.x
var dx:int = lx - rx + 2
fmap(function(t:Tree):void { t.x += dx }, T.right)
T.x = (T.left.x + T.right.x) / 2
}
}
public function adjustRoot(T:Tree):void {
var x0:int = T.x
fmap(function(t:Tree):void { t.x -= x0 }, T)
}
public function fmap(f:Function, t:Tree):void {
if(t){
f(t)
if(t.left) fmap(f, t.left)
if(t.right) fmap(f, t.right)
}
}
}
}
class Tree {
public var left:Tree
public var right:Tree
public var parent:Tree
public var x:int
public function Tree() {
//
}
public function get leftmost():Tree {
var t:Tree = this, s:Tree
while(t.left) t = t.left
if(t.right){
s = t.right.leftmost
if(s.x < t.x) t = s
}
return t
}
public function get rightmost():Tree {
var t:Tree = this, s:Tree
while(t.right) t = t.right
if(t.left){
s = t.left.rightmost
if(s.x > t.x) t = s
}
return t
}
}