js javascript二叉の木の並べ替え
1973 ワード
二叉樹(Binary Search Tree)または一本の空き木、または以下の性質を持つ二叉の木:左のサブツリーが空でない場合、左のサブツリーのすべてのノードの値は、そのルートノードの値よりも小さい. 右のサブツリーが空でない場合、右のサブツリーのすべての接合点の値は、そのルートノードの値よりも大きい. その左、右の木もそれぞれ二叉の並べ替えツリーです. コードの実装は以下の通りです.
function Node()
{
this.left=null;
this.right=null;
this.value=null;
}
Node.prototype.add=function(value)//
{
if(value!=null && typeof value != 'undefined')
{
if(this.value==null)
{
this.value=value;
return ;
}
var node=new Node();
node.value=value;
if(this.value >= value)// on left
{
if(this.left==null)
{
this.left=node;
}
else
{
this.left.add(value);
}
}
else // on right
{
if(this.right==null)
{
this.right=node;
}
else
{
this.right.add(value);
}
}
}
}
Node.prototype.print=function(data)//
{
//if((typeof data == 'undefined') || !(data instanceof Array) )return;
if(this.left!=null)
{
this.left.print(data);
}
data.push(this.value);
if(this.right!=null)
{
this.right.print(data);
}
}
function app()
{
var data=[2,6,56,102,5,4,47,7000,200,45,24,85,63,954,6222,5] ;
var root=new Node();
//
for(var i=0;i<data.length;i++)
{
root.add(data[i]);
}
var rs=[];
root.print(rs);
alert(rs.join(","));
}