为了账号安全,请及时绑定邮箱和手机立即绑定
  • <!DOCTYPE html>

    <html lang="en">


    <head>

    <meta charset="UTF-8">

    <title>JavaScript二叉树中序算法</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;

    } else {

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

    insertNode(node.left, newNode);

    }

    } else {

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

    if (node.right === null) {

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

    node.right = newNode;

    } else {

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

    insertNode(node.right, newNode);

    }

    }

    };


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

    this.insert = function (key) {

    var newNode = new Node(key);

    //newNode拥有newNode.key=key,newNode.left=null,newNode.right=null

    if (root === null) {

    root = newNode;

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

    } else {

    insertNode(root, newNode)

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

    }

    };


    //将root根值和传入值(callback)赋给inOrderTraverseNod(),执行inOrderTraverseNod()

    this.inOrderTraverse = function (callback) {

    inOrderTraverseNode(root, callback);

    };

    };


    //传入子节点(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 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);

    });


    //定义callback函数,将传入callback的值打印出来

    var callback = function (key) {

    console.log(key);

    };


    //注意此callback是参数,不是function函数,执行的是inOrderTraverse(),不是上面的callback()

    binaryTree.inOrderTraverse(callback);

    </script>

    </body>


    </html>


    查看全部
  • <!-- 稍微改造了一下下,可视化二叉树排序,非常有利于学习和理解哟!-->

    <!DOCTYPE html>    

    <html>    

    <title>二叉排序树</title>    

        <head>    

            <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />    

        </head>    

        <body >    

            <canvas id="canvas" width="1366" height="768" ></canvas>

        </body>    

    </html>    

        

    <script type="text/javascript">

           

            //二叉算法函数    

           function BinaryTree(){

            //node 节点函数

            var Node=function(key){

                this.key=key;

                this.left=null;

                this.right=null;

                this.x = 0;//图形绘制坐标

                this.y = 0;//图形绘制坐标

            };


            /**二叉树可视图形描述**/

            this.graphical = [];//图形数组

            this.lrMove = 100;//左右偏移量

            this.udMove = 100;//上下偏移量

            /**==================**/


            //定义根节点

            var root=null;


            //插入节点 循环递归函数 左右分插

            this.insertNode=function(node,newNode){

                if(newNode.key < node.key){

                    if(node.left===null){

                        var x = node.x;

                        var y = node.y;

                        newNode.x = (x -= this.udMove); 

                        newNode.y = (y += this.lrMove);

                        node.left=newNode;     

                    }else{

                        this.insertNode(node.left,newNode);

                    }

                }else{

                    if(node.right===null){

                        var x = node.x;

                        var y = node.y;

                        newNode.x = (x += this.udMove); 

                        newNode.y = (y += this.lrMove);

                        node.right=newNode;

                    }else{

                        this.insertNode(node.right,newNode);

                    }

                }

            };


            //入口程序

            this.insert=function(key){

                var newNode= new Node(key);

                if(root===null){

                    root=newNode;

                    root.x = 500;

                    root.y = 100;

                    this.graphical.push(root);

                }else{

                    this.insertNode(root,newNode);

                }

            };


            var inOrdertraverseNode = function(node,callback){

                if(node !== null){

                    inOrdertraverseNode(node.left,callback);

                    callback(node.key);

                    inOrdertraverseNode(node.right,callback);

                }

            }


            this.inOrdertraverse = function(callback){

                inOrdertraverseNode(root,callback);

            }

        }


        var nodes=[8,3,10,1,6,14,4,15,12,13];

        var binaryTree=new BinaryTree;

        for(var i = 0 ; i < nodes.length ; i++){

             binaryTree.insert(nodes[i]);

        }


        var callback = function(key){

            console.log(key)

        }


        binaryTree.inOrdertraverse(callback);


        /*=====================================================开始绘制================================*/

        var canvas = document.getElementById("canvas");

        var context = canvas.getContext('2d');  //获取对应的2D对象(画笔)



        function draw(key,x,y){

            this.counter = 0;

            this.render = function(c){

                c.fillStyle = "hsl("+ this.counter +", 100%, 50%)";

                c.strokeStyle = '#fff'; //设置笔触的颜色

                c.font = "bold 40px '字体','字体','微软雅黑','宋体'"; //设置字体

                c.textBaseline = 'hanging'; //在绘制文本时使用的当前文本基线

                c.fillText(key ,x ,y); 

            }

            this.update = function(){

              this.counter += 5;

            }

        }


        var fontCavaseArr = [];


         function init() { 

            loop();//绘制文字        

            setInterval(run, 1000/30);

          }



        function run(x,y){

          context.fillStyle = "rgba(0,0,0,0.1)";

          context.fillRect(0,0,1366,768); //绘制 1366*768 像素的已填充矩形:

          for (i=0; i<fontCavaseArr.length; i++) {

            var particle = fontCavaseArr[i]; 

            particle.render(context); 

            particle.update(); 

          }

          gLine();//绘制线条

        }


        function loop(){

            font(binaryTree.graphical[0]);

        }


        function font(obj){

            if(obj.key != null && obj.key != undefined){

                var drawFont = new draw(obj.key,obj.x,obj.y);

                fontCavaseArr.push(drawFont);

            }

            if(obj.left != null && obj.left != undefined){

                var drawFont = new draw(obj.left.key,obj.left.x,obj.left.y);

                fontCavaseArr.push(drawFont);

                font(obj.left);

            }

            if(obj.right != null && obj.right != undefined){

                var drawFont = new draw(obj.right.key,obj.right.x,obj.right.y);

                fontCavaseArr.push(drawFont);

                font(obj.right);

            }

        }


        function gLine(){

            line(binaryTree.graphical[0]);

        }

        

        function line(obj){

            context.lineJoin="round";  

            context.lineCap="butt";  

            context.beginPath(); 

            if(obj.left != null && obj.left != undefined){

                context.moveTo(obj.x+20,obj.y+20); 

                context.lineTo(obj.left.x+20,obj.left.y+20);

                context.stroke();  

                context.closePath(); 

                line(obj.left);

            }

            if(obj.right != null && obj.right != undefined){

                context.moveTo(obj.x+20,obj.y+20); 

                context.lineTo(obj.right.x+20,obj.right.y+20);

                context.stroke();  

                context.closePath(); 

                line(obj.right);

            }

        }

        

        init();


    </script>    


    查看全部
  • 1.前序遍历可用于复制一颗二叉树 2.中序便历可用于排序 3.后序遍历可以用在文件系统里
    查看全部
  • 中序遍历,排序 前序遍历,复制 后序遍历,查找最下 二叉树:从根节点开始,当传入的值小于根节点时,放在左边,否则放在右边。若根节点下有(左右)子节点,进一步对其值进行比较,直到叶节点,使其成为叶节点的子节点。 1,中序遍历原理:从根节点开始,先从左子树遍历,遵循从左至右的原则,当遇到叶节点(即没有左右子节点)后,打印当前节点值,并返回到父节点(中间节点),打印当前父节点值,再遍历其右子节点,遇到叶节点后,打印当前节点值,并返回到父节点(中间节点),直到返回到根节点,打印节点值,再遍历右子树,方法与左子树相同。 2,前序遍历原理:从根节点开始,打印当前节点值,之后从左子树遍历,遵循从左至右的原则,无论遇到中间节点还是叶节点,遵循先打印当前节点值,再进行遍历。当遇到叶节点之后,返回到父节点,当左右子节点遍历完之后,回到根节点。 3,后序遍历原理:从根节点开始,先从左子树遍历,遵循从左至右的原则,当遇到叶节点(即没有左右子节点)后,打印当前节点值,并返回到父节点(中间节点),只有父节点的左右子节点遍历完之后,再打印父节点的值。当左右子树均遍历完之后,再打印根节点的值。
    查看全部
  • <!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>



    查看全部
    1. 中序遍历 : 左左左 没有先打印 然后 回去 打印 然后右  左 没有打印 ,有右看右 没有回去。

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

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

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

    5. 中序便历可用于排序

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


    查看全部
  • <!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>


    查看全部
  • 这里漏了吧,不过没关系,也就截图上的内容

    查看全部
    1. 根节点

    2. 中间节点

    3. 叶子结点

    4. 节点层次:二叉树的高

    5. 排序二叉树:左子节点值小于父节点,右子节点值大于父节点

    查看全部
  • 从左到右开始,左小,右大
    查看全部
  • CRV现在利用一些平台的新的框架,嗯,开发出来的程序可以同时应用于安卓平嗯,平板nlss以及电脑上。
    查看全部
  • 在老司out除了可以开发web前端,还可以开发服务器后台恩,他需要用到新的技术note js。
    查看全部
  • 排序二叉树:左孩子 <父节点< 右孩子  兄弟节点   根节点


    查看全部
  • ==用于一般比较,===用于严格比较,==在比较的时候可以转换数据类型,===严格比较,只要类型不匹配就返回flase

    查看全部
  • 前序遍历---相当于复制当前的二叉树

    查看全部
首页上一页123456下一页尾页

举报

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

微信扫码,参与3人拼团

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

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