Binary Tree

二元樹排序法，英文為Binary Tree，近代又譯成黑紅樹，是資料結構裏很重要的課程，現今電腦科學全都建構在這個結構上。另外資料結構是大學資訊系必修科目，因此專列此篇加以說明。

todo–說明原理

完整代碼

class Node(var d:Int, var left:Node?=null, var right:Node?=null)
var index:Int=0
var d: Array<Int>? = null

fun main(args:Array<String>){
    //取得亂數
    getData(10)

    //建立二元樹
    var root:Node?=null
    for (i in d!!.indices){
       root=bt(root, d!![i])
    }

    //排序
    var t1:Long=System.currentTimeMillis()
    sort(root)
    var t2:Long=System.currentTimeMillis()
    println(t2-t1)

    //列印
    for (i in d!!){
        print("%d ".format(i))
    }

}
fun getData(count:Int){
    d=Array(count, {0})
    for (i in d!!.indices){
        d?.set(i, (Math.random()*1000).toInt())
    }
}
fun bt(node:Node?, d:Int):Node{
    var n=node
    if (n ==null)n=Node(d)
    else if (d<n.d)n.left=bt(n.left, d)
    else n.right=bt(n.right, d)
    return n
}
fun sort(node:Node?){
    if(node?.left!=null)sort(node.left)
    d?.set(index++, node!!.d)
    if(node?.right!=null)sort(node.right)
}
結果:
19 52 89 90 247 540 564 571 600 809