二叉树

作者: 六月太阳花 | 来源:发表于2017-01-02 22:21 被阅读0次

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);

相关文章

  • 数据结构与算法-二叉树02

    二叉树的定义 二叉树的特点 二叉树的五中基本形态 其他二叉树 斜二叉树 满二叉树 完全二叉树图片.png满二叉树一...

  • 二叉树

    二叉树 高度 深度真二叉树 满二叉树 完全二叉树 二叉树遍历前序 中序 后序层序遍历 翻转二叉树 递归法...

  • 二叉树 基础操作

    二叉树的使用 二叉树结构 先序创建二叉树 DFS 先序遍历二叉树 中序遍历二叉树 后序遍历二叉树 BFS 层次遍历...

  • 树与二叉树

    **树 ** 二叉树 满二叉树 完全二叉树 三种遍历方法 树与二叉树的区别 二叉查找树 平衡二叉树 红黑二叉树

  • 二叉树的宽度优先搜索(层次遍历,BFS)

    二叉树结构: 二叉树宽度优先搜索: 按照二叉树的层数依次从左到右访问二叉树的节点;例如:给定一个二叉树: 按照宽度...

  • 剑指 offer:39、平衡二叉树

    39. 平衡二叉树 题目描述 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 解题思路: 平衡二叉树:Wiki:在...

  • Algorithm小白入门 -- 二叉树

    二叉树二叉树构造二叉树寻找重复子树 1. 二叉树 基本二叉树节点如下: 很多经典算法,比如回溯、动态规划、分治算法...

  • 14-树&二叉树&真二叉树&满二叉树

    一、树 二、二叉树 三、真二叉树 四、满二叉树

  • 二叉树的应用

    完美二叉树(满二叉树) 除了最下一层的节点外,每层节点都有两个子节点的二叉树为满二叉树 完全二叉树 除二叉树最后一...

  • 12.树Tree(2)

    目录:1.二叉树的基本概念2.二叉树的性质3.二叉树的创建4.二叉树的遍历 1.二叉树的基本概念 2.二叉树的性质...

网友评论

    本文标题:二叉树

    本文链接:https://www.haomeiwen.com/subject/iwhgvttx.html