请教一下,如何实现一个二元查找树,给定一个中数、节点最大值、最小值,随机生成一个二元查找树


最好用JavaScript或Java实现。

我用Javascript实现了这个二元查找树生成器:


 function Tree(root,value){
    Tree.prototype.findMin=function(){
        var tmp=this;
        while (tmp.root!=null&&tmp.root.value>tmp.value){
            tmp=tmp.root;
        }
        if(tmp.root!=null)
        {
            return tmp.root.value;
        }else{
            return min;
        }
    }
    Tree.prototype.findMax=function(){
        var tmp=this;
        while (tmp.root!=null&&tmp.root.value<tmp.value){
            tmp=tmp.root;
        }
        if(tmp.root!=null)
        {
            return tmp.root.value;
        }else{
            return max;
        }
    }
    this.root=root;
    this.value=value;
    var leftValue=null;
    this.left=null;
    var rightValue=null;
    this.right=null;
    if(this.root==null)
    {
        leftValue=Math.floor(Math.random()*(this.value-min));
        rightValue=this.value+1+Math.floor(Math.random()*(max-this.value));
        this.left=new Tree(this,leftValue);
        this.right=new Tree(this,rightValue);
    }

    var mmin=this.findMin();
    leftValue=mmin+Math.floor(Math.random()*(this.value-mmin));
    if(leftValue>mmin)
        this.left=new Tree(this,leftValue);
    var mmax=this.findMax();
    rightValue=this.value+Math.floor(Math.random()*(mmax-this.value));
    if(rightValue>this.value)
        this.right=new Tree(this,rightValue);
}
var middle=10;
var min=0;
var max=middle*2;

console.info(new Tree(null,10))

二元查找树 树形结构 数据结构 算法 JavaScript

Oo凡星oO 9 years, 4 months ago

我觉得没有定义深度啊,那直接生成一个


 middle
        /    \
      min    max

这种形式的东西是正确的吗。

洩矢緅访子 answered 9 years, 4 months ago

Your Answer