二叉树

1>二叉树

        var root = null;
        //添加数据形成二叉树，只考虑所有数据都不相等
        function bt_add(node,n){
            if(root == null){
                        //alert('根节点为空，把 '+n+' 作为根节点');
                        root = {
                                value:n,
                                l:null,
                             r:null
                        };
                }else if(node.value == n){
                        return;
                }else{
                        if(n < node.value){
                                //alert(n + ' 小于 ' + node.value + ',准备向左走！');
                                if(node.l){
                                    //alert('左边没地方了，准备加到 '+node.l.value +'上');
                                    //左边有值
                                    return bt_add(node.l,n);
                            }else{
                                    //alert('左边有地方，加入！');
                                    node.l = {
                                            value:n,
                                            l:null,
                                            r:null
                                    };
                                }
                        }else{
                                //alert(n + ' 大于 ' + node.value + ',准备向右走！');
                                if(node.r){
                                    //alert('右边没地方了，准备加到 '+node.r.value +'上');
                                    return bt_add(node.r,n);
                                }else{
                                    //alert('右边有地方，加入！');
                                    node.r = {
                                            value:n,
                                            l:null,
                                            r:null
                                        };
                                    }
                            }
                    }
        }
        //在二叉树中进行查找
        function bt_find(node,n){
                if(root == null){
                    return false;
                }else if(node.value == n){
                    return true;
                }else{
                        if(n > node.value){
                                //向右去找
                                if(node.r == null){return false;}
                                return bt_find(node.r,n);
                        }else{
                            //向左找
                            if(node.l == null) return false;
                            return bt_find(node.l,n);
                        }
                }
        }

        //测试
        var N = 10000;
        var oTime = new Date().getTime();
        for(var i = 0; i< N; i++){
            bt_add(root,Math.floor(Math.random()*i));
        }
        for(var i = 0; i<N;i++){
            bt_find(root,Math.floor(Math.random()*i));
        }
        alert(new Date().getTime()-oTime);