为了账号安全,请及时绑定邮箱和手机立即绑定
  • 从左到右开始,左小,右大
    查看全部
  • <!DOCTYPE html>

    <html lang="en">

    <head>

    <meta charset="UTF-8" />

    <meta name="viewport" content="width=device-width, initial-scale=1.0" />

    <meta http-equiv="X-UA-Compatible" content="ie=edge" />

    <title>Document</title>

    </head>

    <body>

    <script>

    function BinaryTree() {

    //初始化root根为空值


    var root = null


    //将传入值添加this.key,this.left,this.right属性


    var Node = function(key) {

    this.key = key


    this.left = null


    this.right = null

    }


    //将传入值进行判断,作为父节点的左支或右支


    var insertNode = function(node, newNode) {

    if (newNode.key < node.key) {

    //如果传入值小于父节点,作为左支,不过要先进行判断左支是否已经存在


    if (node.left === null) {

    //如果左支是null空值,将传入值作为左支


    node.left = newNode

    console.log(node.left.key)

    } else {

    //否则(左支已经存在)继续执行函数进行下个节点的判断


    insertNode(node.left, newNode)

    }

    } else {

    //否则(传入值大于父节点)作为右支,不过要先进行判断右支是否已经存在


    if (node.right === null) {

    //如果右支是null空值,将传入值作为右支


    node.right = newNode

    console.log(node.right.key)

    } else {

    //否则(右支已经存在)继续执行函数进行下个节点的判断


    insertNode(node.right, newNode)

    }

    }

    }


    //函数的入口,第一步执行的函数,确定root根的值


    this.insert = function(key) {

    var newNode = new Node(key)

    if (root === null) {

    root = newNode

    console.log(root.key)

    //如果没有root根,将传入值作为root根

    } else {

    insertNode(root, newNode)

    //如果已经存在根,执行insertNode函数

    }

    }


    // 删除二叉树

    this.remove = function(key) {

    root = removeNode(root, key)

    }

    }


    //传入子节点(callback)和父节点(node)(第一次的父节点就是root)

    var inOrderTraverseNode = function(node, callback) {

    //如果父节点存在,继续将左支和右支执行inOrderTraverseNod(),直到不存在子分支为止


    // !!注意if结构里面的函数执行顺序,先执行inOrderTraverseNode(node.left,callback);再执行callback(node.key);最后执行inOrderTraverseNode(node.right,callback);


    //当inOrderTraverseNode(node.left,callback);执行完之后,才会再执行callback(node.key);(即先打印完左分支的值,再打印最顶层的父节点,这样就达到了从小到大的排序效果).右分支同理


    if (node !== null) {

    inOrderTraverseNode(node.left, callback)


    callback(node.key)


    inOrderTraverseNode(node.right, callback)

    }

    }

    var findMinNode = function(node) {

    if (node) {

    while (node && node.left !== null) {

    node = node.left

    }

    return node

    }

    return null

    }

    TODO:;

    // 删除二叉树

    var removeNode = function(node, key) {

    if (node === null) {

    return null

    }

    if (key < node.key) {

    node.left = removeNode(node.left, key)

    return node

    } else if (key > node.key) {

    node.right = removeNode(node.right, key)

    return node

    } else {

    // 这事判断第一种情况,没有左右分支的情况下,

    if (node.left === null && node.right === null) {

    node = null

    return node

    }

    // 这是左子树为空的情况

    if (node.left === null) {

    node = node.right

    return node

    } else if (node.right === null) {

    // 这是右子树为空的情况

    node = node.left

    return node

    }

    // 如果左右两个分支都存在的时候,那么执行下面的代码

    var aux = findMinNode(node.right)

    node.key = aux.key

    node.right = removeNode(node.right, aux.key)

    return node

    }

    }

    //

    var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]


    //实例化BinaryTree


    var binaryTree = new BinaryTree()


    //遍历nodes数组,将每个数组的值(key)传入binary.insert(),执行 insert()函数


    nodes.forEach(function(key) {

    binaryTree.insert(key)

    })


    console.log(binaryTree.remove(10))

    </script>

    </body>

    </html>



    查看全部
  • CRV现在利用一些平台的新的框架,嗯,开发出来的程序可以同时应用于安卓平嗯,平板nlss以及电脑上。
    查看全部
  • 在老司out除了可以开发web前端,还可以开发服务器后台恩,他需要用到新的技术note js。
    查看全部
    1. 中序遍历 : 左左左 没有先打印 然后 回去 打印 然后右  左 没有打印 ,有右看右 没有回去。

    2. 前序遍历 :先打印根,然后左 打印 ,再左打印,然后看看有没有左没有就看右 右有打印 然后这个节点没有左右就回去 ,再回去 ,再看看右有没有,然后和前面一样。

    3. 后续遍历 :一直看左 打印左, 然后返回看右 的左 打印 再看右的右 是叶子节点就打印自己 然后发挥 本节点 而且它的左右都打印完了就打印自己。

    4. 前序遍历可用于复制一颗二叉树

    5. 中序便历可用于排序

    6. 后序遍历可以用在文件系统里


    查看全部
  • <!DOCTYPE html>
    
    <html>
    
        <head>
            <meta charset="utf-8" />
            <title>Binary Tree</title>
        </head>
    
        <body>
            <script>
                /**
                 * 二叉排序树
                 * 新插入的数据只是增加在原先的树上(新加入的结点找到一个位置,作为原先树上某个结点的孩子结点)
                 * 并不会破坏之前已形成的树
                 */
                var Node = function(key) {
                    this.key = key;
                    this.left = null;
                    this.right = null;
                }; // var Node end
                // nodes数组存储一下待排序的数据
                var nodes = [
                    8,
                    3,
                    10,
                    1,
                    6,
                    14,
                    4,
                    7
                ];
    
                // 新建一个排序树对象,是个函数对象
                var binaryTree = new BinaryTree();
    
                // 利用数组的forEach函数,依次处理数组中的数据,按下标
                nodes.forEach(function(key) {
                    // 对于数组中的每一个值,进行二叉排序树的插入操作
                    binaryTree.insert(key);
                });
    
                // 
                
                var callback = function(key) { // 1
                    console.log(key);
                }
                binaryTree.inOrderTraverse(callback); // 1
    
                function BinaryTree() {
    
                    var root = null;
    
                    // 将数组转换为二叉排序树
                    this.insert = function(key) {
                        var newNode = new Node(key);
                        if(root === null) {
                            root = newNode;
                        } else {
                            insertNode(root, newNode);
                        }
    
                    };
                    var insertNode = function(node, newNode) { // 递归地进行节点的插入
                        if(newNode.key < node.key) { // 如果新节点的值小于这个节点的父节点
                            if(node.left === null) {
                                // 如果父节点左孩子节点为空,则将新节点置为左孩子节点
                                node.left = newNode;
                            } else {
                                insertNode(node.left, newNode);
                            }
                        } else {
                            if(node.right === null) {
                                node.right = newNode;
                            } else {
                                insertNode(node.right, newNode);
                            }
                        }
                    }; // var insertNode end
    
                    // 中序遍历
                    this.inOrderTraverse = function(callback) { // callback是一个输出语句方法参数
                        inOrderTraverseNode(root, callback);
                    };
    
                    var inOrderTraverseNode = function(node, callback) { // node节点为根节点
                        if(node !== null) { // 如果根节点不为空,即树存在时,进行先左,在中,在右,并递归
                            inOrderTraverseNode(node.left, callback);
                            // 输出节点中的key值
                            callback(node.key);
                            // 这是外部的一个函数  var callback = function(key) 这里的意思是,上一句进入左子树,如果上一句的结点没有左子树的话,就打印是一个结点
                            /**
                             * 
                             *inOrderTraverse中的callback参数的意义何在?
                             *睡了一觉,自己悟出来了。传入的callback,实际上就是老师定义的callback函数,
                             *因为老师的callback函数是定义在binarytree外部的,所以他把这个函数传进去,以便后续调用。
                             *我自己的代码,把callback函数定义在binarytree内部了,所以我不传callback参数是没有任何问题的,但是我的callback函数在其它地方就无法调用了。...
                             *
                             *callback只是一个引用,你也可以改成其他名字。为什么要用callback是因为程序员的习惯吧,大家一看就知道这里是一个回调函数。 
                             *var声明的函数和this来声明的函数作用域不一样,var声明的在外面无法调用才对,你可以试试,我没验证。。。。。。。...
                             */
                            inOrderTraverseNode(node.right, callback);
                        }
                    };
                }
            </script>
    
        </body>
    
    </html>


    查看全部
  • <!DOCTYPE html>
    <html lang="en">
    <head>
        <meta charset="UTF-8">
        <title>Title</title>
    </head>
    <body>
    <script type="text/javascript">
        function binaryTree() {
            /**
             * 定义节点
             * @param key int|float 节点值
             */
            var node = function (key) {
                this.key = key;
                this.left = null;
                this.right = null;
            }
    
            //定义根节点
            var root = null;
    
            /**
             * 定义插入属性
             * @param key int|float 要插入的值
             */
            this.insert = function (key) {
                var newNode = new node(key);
                if (root === null) {
                    root = newNode;
                } else {
                    insertNoder(root, newNode);
                }
            }
    
            /**
             * 插入数据 小左大右
             * @param node obj 节点数据
             * @param newNode obj 要插入的节点数据
             */
            var insertNoder = function (node, newNode) {
                if (newNode.key < node.key) {
                    if (node.left === null) {
                        node.left = newNode;
                    } else {
                        insertNoder(node.left, newNode);
                    }
                } else {
                    if (node.right === null) {
                        node.right = newNode;
                    } else {
                        insertNoder(node.right, newNode);
                    }
                }
            }
    
            /**
             * 查找节点
             * @param key int|float 查找的节点值
             * @param node obj 节点
             * @returns obj|null 查找的节点, 不存在返回null
             */
            this.find = function (key, node = root) {
                return findNode(key, node)[1];
            }
    
            /**
             * 判断节点是否存在
             * @param key int|float 查找的节点值
             * @param node obj 节点
             * @returns bool 存在true, 不存在false
             */
            this.exists = function (key, node = root) {
                return findNode(key, node)[0];
            }
    
            /**
             * 查找节点
             * @param key int|float 查找的节点值
             * @param node obj 节点
             * @returns array
             */
            var findNode = function (key, node) {
                if (node === null) return [false, null];
                if (key == node.key) return [true, node];
                if (key < node.key) return findNode(key, node.left);
                return findNode(key, node.right);
            }
    
            /**
             * 中序排列查询
             * @param node obj 节点
             * @returns {Array}
             */
            this.inOrder = function (sort = 'ASC', node = root) {
                var nodeArr = [];
                if (node !== null) {
                    if (sort.toUpperCase() == 'DESC') {
                        inOrderDescNode(node, nodeArr);
                    } else {
                        inOrderAscNode(node, nodeArr);
                    }
                }
                return nodeArr;
            }
    
            /**
             * 中序查询-升序(左->中->右)
             * @param node obj 节点
             * @param nodeArr array 存储排序的值
             */
            var inOrderAscNode = function (node, nodeArr) {
                if (node !== null) {
                    inOrderAscNode(node.left, nodeArr);
                    nodeArr.push(node.key)
                    inOrderAscNode(node.right, nodeArr);
                }
            }
    
            /**
             * 中序查询-降序(右->中->左)
             * @param node obj 节点
             * @param nodeArr array 存储排序的值
             */
            var inOrderDescNode = function (node, nodeArr) {
                if (node !== null) {
                    inOrderDescNode(node.right, nodeArr);
                    nodeArr.push(node.key);
                    inOrderDescNode(node.left, nodeArr)
                }
            }
    
            /**
             * 前序查询
             * @param node obj 节点
             * @returns {Array}
             */
            this.preOrder = function (node = root) {
                var nodeArr = [];
                if (node !== null) {
                    preOrderNode(node, nodeArr);
                }
                return nodeArr;
            }
    
            /**
             * 前序(中->左->右)
             * @param node obj 节点
             * @param nodeArr 存储查询的值
             */
            var preOrderNode = function (node, nodeArr) {
                if (node !== null) {
                    nodeArr.push(node.key);
                    preOrderNode(node.left, nodeArr);
                    preOrderNode(node.right, nodeArr)
                }
            }
    
            /**
             * 后序查询
             * @param node obj 节点
             * @returns {Array}
             */
            this.reOrder = function (node = root) {
                var nodeArr = [];
                if (node !== null) {
                    reOrderNode(node, nodeArr);
                }
                return nodeArr;
            }
    
            /**
             * 后序(左->右->中)
             * @param node obj 节点
             * @param nodeArr 存储查询的值
             */
            var reOrderNode = function (node, nodeArr) {
                if (node !== null) {
                    reOrderNode(node.left, nodeArr);
                    reOrderNode(node.right, nodeArr);
                    nodeArr.push(node.key);
                }
            }
    
            /**
             * 最大值
             * @param node obj 节点
             * @returns {*}
             */
            this.max = function (node = root) {
                var newNode = maxNode(node);
                return newNode === null ? null : newNode.key;
            }
    
            /**
             * 查找一个节点最大的值
             * @param node obj 节点
             * @returns {*}
             */
            var maxNode = function (node) {
                if (node === null) return null;
                while (node !== null && node.right !== null) {
                    node = node.right;
                }
                return node;
            }
    
            /**
             * 最小值
             * @param node obj 节点
             * @returns {*}
             */
            this.min = function (node = root) {
                var newNode = minNode(node);
                return newNode === null ? null : newNode.key;
            }
    
            /**
             * 查找一个节点最小值
             * @param node obj 节点
             * @returns {*}
             */
            var minNode = function (node) {
                if (node === null) return null;
                if (node.left !== null) return minNode(node.left);
                return node;
            }
    
            /**
             * 移除一个节点
             * @param key int|float 要移除的节点值
             * @param node obj 节点
             * @returns {*}
             */
            this.remove = function (key, node = root) {
                return removeNode(key, node);
            }
    
            /**
             * 移除节点
             * @param key int|float 要移除的节点值
             * @param node obj 节点
             * @returns {*}
             */
            var removeNode = function (key, node) {
                if (node === null) return null;
                if (key === node.key) {
                    if (node.left === null && node.right === null) return null;
                    if (node.left === null) return node.right;
                    if (node.right === null) return node.left
                    var aux = minNode(node.right);
                    node.key = aux.key;
                    node.right = removeNode(node.right, aux.key);
                    return node;
                }
                if (key < node.key) {
                    node.left = removeNode(key, node.left);
                    return node;
                }
                node.right = removeNode(key, node.right);
                return node;
            }
        }
    
        var arr = [9, 7, 4, 4, 6.4, 5, 8, 3.2, 11, 15, 9, 5, 6, 0, 3, 2, 13, 3.6, 1, 12, 14];
        var node = new binaryTree();
        //循环插入数据
        arr.forEach(function (key) {
            node.insert(key);
        })
        console.log('exists: ', node.exists(9));
        console.log('exists-100: ', node.exists(100));
        console.log('find: ', node.find(9));
        console.log('find-1000: ', node.find(1000));
        console.log('inOrder-Asc: ', node.inOrder());
        //js实现对象的复制,不影响原对象
        //var newNode = Object.assign({}, node.find(4));//
        var newNode = JSON.parse(JSON.stringify(node.find(4)));//当源对象的属性值是一个指向对象的引用时,应用深度复制
        console.log('inOrder-Asc-4: ', node.inOrder('ASC', newNode));
        console.log('remove-2: ', node.remove(2,newNode));
        console.log('remove-3: ', node.remove(3));
        console.log('remove-15: ', node.remove(15));
        console.log('inOrder-Asc: ', node.inOrder());
        console.log('inOrder-Asc-4: ', node.inOrder('ASC', newNode));
        console.log('inOrder-desc: ', node.inOrder('DESC'));
        console.log('inOrder-desc-11: ', node.inOrder('DESC', node.find(11)));
        console.log('preOrder: ', node.preOrder());
        console.log('reOrder: ', node.reOrder());
        console.log('max: ', node.max());
        console.log('max-4: ', node.max(node.find(4)));
        console.log('min: ', node.min());
        console.log('min-11: ', node.min(node.find(11)));
        console.log('min-11: ', node.max(null));
    </script>
    </body>
    </html>


    查看全部

举报

0/150
提交
取消
课程须知
1、对html基础知识已经掌握。 2、对js的基本语法,例如数组,对象有一定的掌握。
老师告诉你能学到什么?
1、二叉树的定义,创建以及js编码实现 2、二叉树中序遍历的算法原理及js编码实现 3、二叉树前序遍历的算法原理及js编码实现 4、二叉树后续遍历的算法原理及js编码实现 5、二叉树节点查找的算法原理和编码实现

微信扫码,参与3人拼团

意见反馈 帮助中心 APP下载
官方微信
友情提示:

您好,此课程属于迁移课程,您已购买该课程,无需重复购买,感谢您对慕课网的支持!