记录学习 JavaScript 二叉树

记录学习 JavaScript 二叉树

自己也做了一段时间编程了,没有系统学习计算机的相关知识,现在仅凭,对编程的爱好,慢慢前进。

现在算是,有一点能力了。

但是,数据结构,还是有点欠缺的。

还好对于面向对象有点了解,现在就把老师用面向过程写的二叉树,用面向对象重写,毕竟面向对象,是现在,解决问题的有效的方式。

原课程地址: Javascript实现二叉树算法

改用面向对象写出来后发现扩展和使用起来非常方便,比如获取降序升序数组,

生成排序二叉树: var s = new bTree([8,6,2,4,7,5,6,7,9,5,2,3,4]);

获取降序数组: var down = s.down();

获取升序数组:var up = s.up();

面向对象的好处之一,每个节点都会有相应方法,比如这样:

获取父节点 左侧降序: var leftDown = s.left.down();

获取父节点 右侧升序:var rightUp = s.right.up();

还可以这样,获取父节点,左侧节点 的 右侧节点 的升序:

var lrUp = s.left.right.up(); (前提是 你要有那个节点)

这里可以扩展出方法 传入一个获取顺序,这个方法 按照这个顺序在自身上查询排序,如果没有返回空数组或者false;

        /**
         * 二叉树类
         * @Author   杰
         * @DateTime 2018-11-10T01:47:21+0800
         * @param    {number | string | array}    arr 如果是 array  初始化一个排序二叉树
         *                                            如果是 number 会生成一个树叶 key 为arr
         *                                            如果是 string 尝试转换为 number 
         *                                                 失败 返回一个 bTree 对象
         *                                                 但是 key 没有值,不会影响生成逻辑,生成逻辑判断key没有值会优先赋值
         * @return   {[object]}                     [bTree 对象]
         */
        function bTree(arr){
            if(Array.isArray(arr)){
                this.arr = arr;
                this._init();
                return this;
            }
            if(!Number.isInteger(arr)){
                arr = parseFloat(arr);
                if(isNaN(arr)){
                    return false;
                }
            }
            this.key = arr;
        }

        bTree.prototype = {
            constructor:bTree,
            /**
             * 如果传入是一个 数组 会调用这个执行生成 二叉树逻辑
             * @Author   杰
             * @DateTime 2018-11-10T01:52:54+0800
             * @return   {[void]}
             */
            _init(){
                if(this.key || !Array.isArray(this.arr)){
                    return false;
                }
                this.arr.forEach(function (v, k) {
                    this._each(v);
                }.bind(this));
                delete this.arr;
            },
            /**
             * 二叉树生成核心逻辑
             * @Author   杰
             * @DateTime 2018-11-10T01:53:43+0800
             * @param    {number}                 value 传入的数值,用于生成二叉树
             * @return   {object}                       this
             */
            _each(value) {
                if(!this.key){
                    this.key = value;
                    return this;
                }
                if(this.key > value) {
                    if(!this.left){
                        return this._setKey('left', value);
                    }
                    return this.left._each(value);
                } else if(this.key < value) {
                    if(!this.right){
                        return this._setKey('right', value);
                    }
                    return this.right._each(value);
                }
                if(!this.left){
                    return this._setKey('left', value);
                }
                if(!this.right){
                    return this._setKey('right', value);
                }
                var l = this.left;
                this._setKey('left', value);
                this.left.left = l;
                return this;
            },
            /**
             * 构造一个含有 value 值的 对象 放在 name 属性上
             * @Author   杰
             * @DateTime 2018-11-10T01:55:12+0800
             * @param    {string}                 name  属性名
             * @param    {number}                 value 二叉树对象的 key 值
             */
            _setKey(name, value) {
                this[name] = new this.constructor(value);
                return this;
            },
            /**
             * 升序遍历二叉树
             * @Author   杰
             * @DateTime 2018-11-10T01:56:41+0800
             * @return   {[array]}                 [升序排序的数组]
             */
            up(ret){
                ret =  ret || [];
                if(this.left){
                    this.left.up(ret);
                }
                // console.log(this.key);
                ret.push(this.key);
                if(this.right){
                    this.right.up(ret);
                }
                return ret;
            },
            /**
             * 降序遍历二叉树
             * @Author   杰
             * @DateTime 2018-11-10T01:57:00+0800
             * @return   {[array]}                 [降序排序的数组]
             */
            down(ret) {
                ret = ret || [];
                if(this.right){
                    this.right.down(ret);
                } 
                // console.log(this.key);
                ret.push(this.key);
                if(this.left){
                    this.left.down(ret);
                }
                return ret;
            },
            /**
             * 安全获取 升序 排序 二叉树 通过这个函数 不会报错 但是 没有值是 undefined
             * @Author   杰
             * 参数 灵活传入 可以传入一个参数用 “.” 隔开 或多个 参数 用点隔开 
             * 如 getUp('left.right.left') 或者 getUp('left.right', 'left', 'right.left')
             * @DateTime 2018-11-10T03:05:38+0800
             * @return   {[type]}                 [description]
             */
            getUp() {
                var arr = this._parseArg.apply(this, arguments);
                var ret = this._parseObj(arr);
                if(!ret){
                    return ret;
                }
                return ret.up();
            },
            /**
             * 安全获取 降序 排序 二叉树 通过这个函数 不会报错 但是 没有值是 undefined
             * @Author   杰
             * 参数 灵活传入 可以传入一个参数用 “.” 隔开 或多个 参数 用点隔开
             * 如 getDown('left.right.left') 或者 getDown('left.right', 'left', 'right.left')
             * @DateTime 2018-11-10T03:07:18+0800
             * @return   {[array | undefined]}
             */
            getDown() {
                var arr = this._parseArg.apply(this, arguments);
                var ret = this._parseObj(arr);
                if(!ret){
                    return ret;
                }
                return ret.down();
            },
            /**
             * 格式化参数
             * @Author   杰
             * @DateTime 2018-11-10T03:10:38+0800
             * @return   {[array]}
             */
            _parseArg() {
                var arg = Array.prototype.join.call(arguments, '.');
                var r = /([^\.]+)+/gi;
                var arr = arg.match(r);
                return arr;
            },
            /**
             * 通过参数数组获取二叉树对象
             * @Author   杰
             * @DateTime 2018-11-10T03:11:19+0800
             * @param    {[array]}                 arr [description]
             * @return   {[object | undefined]}
             */
            _parseObj (arr) {
                if(!Array.isArray(arr)){
                    return undefined;
                }
                arr.forEach(function (v, k) {
                    if(v!=='left' && v!=='right'){
                        return true;
                    }
                    if(!ret[v]){
                        ret = undefined;
                        return false;
                    }
                    ret = ret[v];
                });
                return ret;
            }
        };

        var arr = [3,10,1,6,4,7,13,14, 3, 8, 9];

        var b = new bTree(arr);

阿杰博客
请先登录后发表评论
  • latest comments
  • 总共0条评论