最新公告
  • 欢迎您光临起源地模板网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入钻石VIP
  • [数据结构与算法-小白系列]第3️⃣天树

    正文概述 掘金(刘小灰)   2020-11-26   816

    树的定义

    数据结构中的树结构和我们现实中的树非常类似,学习的时候完全可以进行类比学习

    数据结构中的,把现实中树的根抽象为根结点,树枝抽象为,树枝的两个端点抽象为结点,树叶抽象为叶子结点,然后整体在整体翻转180度,就得到了数据结构中的[数据结构与算法-小白系列]第3️⃣天树

    除此之外,树还有以下几个概念高度,深度,

    一图胜过千言万语

    [数据结构与算法-小白系列]第3️⃣天树

    对着图看文字解释,加深理解

    • 高度 节点到叶子节点最长路径
    • 深度 根节点到这个节点所经历边的个数
    • 层 深度+1

    什么是二叉树

    很好理解,每个节点 最多 有两个"叉"的树就是二叉树。其中,二叉树又分为 满二叉树完全二叉树

    • 满二叉树

    叶子节点全都在最底层,除了叶子节点之外,每个节点都有左右两个子节点

    • 完全二叉树

    叶子节点都在最底下两层,最后一层的叶子节点都靠左排列,并且除了最后一层,其他层的节点个数都要达到最大

    一图胜过千言万语

    [数据结构与算法-小白系列]第3️⃣天树

    其中我们把 左子树上所有结点的数据域都小于等于根结点的数据域,右子树上所有结点的数据域都大于等于根结点的数据域 的二叉树称之为二叉搜索树

    一图胜过千言万语

    [数据结构与算法-小白系列]第3️⃣天树

    使用javascript实现二叉搜索树

    在写代码之前我们先分析下二叉搜索树这种数据结构的特点如何使用编程思想表达出来

    • 首先我们需要一个创建节点的,并且每个节点都有leftright属性及自身存放的数据key
    function Node(data){
        this.key = data;
        this.left=null; // 左节点
        this.right=null; // 右节点
    }
    
    
    • 递归遍历整棵树,找到需要插入数据对应的地方
    情况1: 如果为空树直接插入
    情况2: 逐层递归遍历节点,把小数插入到最左边,大数插入到最右边
    

    开始撸代码(注释已给出)

    
    function searchTree() {
      // 树的节点
      function Node(data) {
        this.key = data;
        this.left = null;
        this.right = null;
      }
      //定义树的根节点
      this.root = null;
      //插入方法
      searchTree.prototype.inster = function (key) {
        const newNode = new Node(key);
        // 如果是空树,直接把当前值赋值给root
        if (this.root === null) {
          this.root = newNode;
        } else {
          this.insterNode(this.root, newNode);
        }
      };
      searchTree.prototype.insterNode = function (node, newNode) {
        // todo 递归查找当前数据应该在的位置
        if (newNode.key > node.key) {
          // 把新节点放到最右边
          if (node.right === null) {
            node.right = newNode;
          } else {
            this.insterNode(node.right, newNode);
          }
        } else {
          // 把新节点放到左端
          if (node.left === null) {
            node.left = newNode;
          } else {
            this.insterNode(node.left, newNode);
          }
        }
      };
    }
    

    二叉搜索树的遍历

    为什么要遍历?

    遍历就是为了按照某种顺序获得到全部数据,其中二叉搜索树本身就是按照顺序存储数据的,所以遍历二叉搜索树更有实际意义

    按照根结点的输出位置,遍历又大致可以分为以下几种

    • 先序遍历
    • 中序遍历
    • 后序遍历

    一图胜过千言万语

    [数据结构与算法-小白系列]第3️⃣天树

    使用javascript实现二叉搜索树遍历

    先序遍历

    // handler用于接收处理遍历数据的函数
      searchTree.prototype.Preorder = function (handler) {
        this.preOrderNode(this.root, handler);
      };
      searchTree.prototype.preOrderNode = function (node, handler) {
        if (node != null) {
          handler(node.key);  // 先序
          this.preOrderNode(node.left, handler);
          this.preOrderNode(node.right, handler);
        }
      };
    

    中序遍历

    // handler用于接收处理遍历数据的函数
      searchTree.prototype.Middle = function (handler) {
        this.preOrderNode(this.root, handler);
      };
      searchTree.prototype.MiddleNode = function (node, handler) {
        if (node != null) {
          this.preOrderNode(node.left, handler);
          handler(node.key); // 中序
          this.preOrderNode(node.right, handler);
        }
      };
    

    后序遍历

    // handler用于接收处理遍历数据的函数
      searchTree.prototype.After = function (handler) {
        this.preOrderNode(this.root, handler);
      };
      searchTree.prototype.AfterNode = function (node, handler) {
        if (node != null) {
          this.preOrderNode(node.left, handler);
          this.preOrderNode(node.right, handler);
          handler(node.key);  // 后序
        }
      };
    

    测试

    let s = new searchTree();
    s.inster(10);
    s.inster(8);
    s.inster(7);
    s.inster(6);
    s.inster(12);
    s.inster(14);
    //中序遍历
    s.Middle(function (val) {
      console.log(val);
    });
    console.log(s);
    

    结果

    [数据结构与算法-小白系列]第3️⃣天树

    可以看出,中序遍历正好是数据从大到小排序好的结果

    理解二叉平衡树(红黑树)

    为什么会有平衡二叉树?

    如果我们使用树结构存储这样一组数据1,2,3,4,5,6

    [数据结构与算法-小白系列]第3️⃣天树

    如果这样的数据量非常大呢? 这时树的深度就会变的非常深,对应的递归遍历整个树的效率就会变的比较低,所有我们需要引入平衡因子

    什么是平衡二叉树

    二叉树中任意一个节点的左右子树的高度相差不能大于 1 其中1可以理解为最优结果,也就是说,树的左右节点存放的数据基本相等,这个时候可以保证树的深度最小,效率最高

    红黑树是怎样做到自平衡的

    首先说说红黑树的性质

    • 性质1:每个节点要么是黑色,要么是红色。
    • 性质2:根节点是黑色。
    • 性质3:每个叶子节点是黑色。
    • 性质4:每个红色结点的两个子结点一定都是黑色。
    • 性质5:任意一结点到每个叶子结点的路径都包含数量相同的黑

    红黑树只要时刻满足这些约束,就可以达到自平衡,其中自平衡常见的操作有变色,左旋转,右旋转,实现原理也比较复杂,在这里就不进行源码实现了

    其他方法实现

    上面我们实现了二叉搜索树的插入和遍历,还有在树中查找一个键,查找最大值,最小值从树中移除某个键等方法在文章中没有实现,完整的源码已经放到github,感兴趣的可以自取研究哦

    最后

    吃不了学习的苦,就要吃生活的苦

    如果此文对你有帮助,记得点赞关注哦?


    起源地 » [数据结构与算法-小白系列]第3️⃣天树

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发?
    请QQ联系我们

    发表评论

    还没有评论,快来抢沙发吧!

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元