计算机中的树【附有示例:JS实现的文件管理器】

自然界的树,不需要我来解释。不过对于计算机中的树结构,可难倒了一大片人。其实,我们日常生活中会经常接触到树结构。

比如,一个公司的结构划分。公司最大的当然是老板了,老板将公司划分为多个大部门,各个大部门下又划分为多个小部门,而每个小部门内部还可能会划分为多个小组,组内还会根据工作种类的不同划分为不同的岗位。这里,如果需要查询这个公司总共有多少岗位,你会怎么办?想想都头大啊。

再比如,我们计算机中存储文件的时候,一个文件夹下面有多个子文件夹,而这些子文件夹还会有其他子子文件夹,还可能会有更多。如果我们要找某个文件,在不知道它在哪个文件夹的时候,我们会使用计算机的搜索功能。那么,计算机如何来实现这个功能呢?想想都头大啊。

这篇文章就来介绍一下我用JS实现的树结构及其常用操作。

介绍

了解一点计算机的朋友都知道,树是由一堆具有相同结构的元素嵌套而来的。它根据不同的特性分为很多的种类,比如二叉树,满树,红黑树,B树,B+树等等等。而树的嵌套结构就决定了,它相关的算法多数可以通过递归来解决,比如二叉树的先序遍历、中序遍历等。

废话不多说了,直接来看看实现代码吧。

实现一棵树

一棵树最重要的东西就是它的节点了,包括当前节点及其子节点,另外还需要一个ID来唯一标识每一个节点。所以我这里的节点如下:

var nodeID = 1;

Ycc.Tree = function() {
   
   /**
    * 节点的自增ID,不允许修改,且每个对象必须唯一
    * @type {number}
    */
   this.$id = nodeID++;

   /**
    * 节点的父节点ID,不允许修改
    * @type {null|Ycc.Tree}
    */
   this.$parentID = null;
   
   /**
    * 节点的子节点列表
    * @type {Array}
    */
   this.children = [];
   
   /**
    * 节点所携带的数据
    * @type {any}
    */
   this.data = null;
   
};

上面代码中Ycc为一个全局变量,是我真正做的一个项目名,可以忽略。

可以看到,这里除了自己的ID外,还使用了parentID,这样在寻找父节点的时候会非常方便。

另外,借助js的灵活性,直接使用children数组表示当前节点的子节点。

如果我告诉你,一棵树我们就写完了,你会感到惊讶吗?

事实确实如此,树是一个集合的概念,集合内元素的结构就决定了树的结构。只是,如果这样我们就需要手动的去设置ID和parentID,以此来保证它们的嵌套。

所以,为了丰富一棵树,我们还需要新增一些便利的方法,来保证树的特性,而不用手动去设置。

给树添加常用的操作

操作一:根据json初始化一棵树

在js及其他语言中,最常用的数据结构莫过于json了。比如,如下结构是示例中的一个json,我们会根据它来生成对应的树。

{
   data:'/',
   children:[
      {
         data:"a",
         children:[
            {
               data:"d",
               children:[
                  {
                     data:"g"
                  },
                  {
                     data:"h"
                  },
                  {
                     data:"i"
                  },
               ]
            },
            {
               data:"e",
               children:[
                  {
                     data:"j"
                  },
                  {
                     data:"k"
                  },
                  {
                     data:"l"
                  },
               ]
            },
            {
               data:"f"
            },
         ]
      },
      {
         data:"b",
         children:[
            {
               data:"m"
            },
            {
               data:"n"
            },
         ]
      },
      {
         data:"c",
         children:[
            {
               data:"o"
            },
            {
               data:"p"
            },
            {
               data:"q"
            },
         ]
      }
   ]
}

这里的实现代码如下:

Ycc.Tree.createByJSON = function (json) {
   var root = new Ycc.Tree();
   root.data = json.data;
   if(Ycc.utils.isArray(json.children) && json.children.length>0){
      for(var i=0;i<json.children.length;i++){
         root.addChildTree(Ycc.Tree.createByJSON(json.children[i]));
      }
   }
   return root;
};

上面代码,第2行,新建了一个root,表示这棵树的根节点,并在第3行将json中的数据附加给节点。

第4行判断节点是否有子节点,如果有子节点,在第5~7行我们递归调用方法createByJSON来为每一个子节点创建一颗子树,并调用addChildTree方法添加到我们的root。

最后返回了我们的树根。

这个addChildTree方法,我们暂时只需知道,它的作用是给当前节点添加一颗子树,稍后给出其实现。

可以看出,这段代码很明显的使用了分治算法策略。

即,将我们的问题分解成多个子问题,子问题使用相同的解决方法(createByJSON),待子问题解决完之后,将子问题合并(addChildTree),即可解决我们的原问题。

操作二:添加一颗子树

Ycc.Tree.prototype.addChildTree = function (tree) {
   if(tree.$parentID) return console.error("sub tree's parent has exist! can't add!",tree);
   tree.$parentID = this.$id;
   this.children.push(tree);
   return this;
};

添加子树,实质上只是添加一个节点ID的引用,即ID和parentID之间的关联关系。

上面代码中,第2行判断了树根,第3~4行就是在操作它们的关联关系。

操作三:获取树的最大深度

树的最大深度是指,从树根开始向下,总共有多少层级。

比如,我们文章开头,对于公司示例,因为有可能有的大部门不划分小部门,这个最大深度是指公司最多划分了几层。

对于文件夹示例,因为有的文件夹可能为空,这个最大深度是指文件夹最多能点到哪儿。

实现代码如下:

Ycc.Tree.prototype.getDepth = function () {
   var self = this;
   var dep = 1;
   if(self.children.length>0){
      for(var i=0;i<self.children.length;i++){
         var subDep = self.children[i].getDepth();
         dep = subDep+1>dep?subDep+1:dep;
      }
   }
   return dep;
};

这个地方也用到了分治策略。

第4行判断有没子级,第5~7行求出子级的最大深度,将其加1与当前最大深度做比较,取最大值即为我们所求的最大深度。

操作四:树的遍历

我总共写了四种遍历方法。分别是:普通遍历  左子树优先遍历  右子树优先遍历  按层级向下遍历。

这里贴一个普通遍历,感兴趣的可以看看其他的遍历方式。

Ycc.Tree.prototype.itor = function (option) {
   var self = this;
   function each(cb) {
      if(cb.call(self,self)) return true;
      if(self.children.length>0){
         for(var i=0;i<self.children.length;i++){
            if(self.children[i].itor().each(cb)) return true;
         }
      }
      return false;
   }
}

地址为:https://github.com/lizhiqianduan/ycc/blob/develop/src/Ycc.Tree.class.js

总结

对于程序员,树结构是经常遇到的,我们的HTML文档就是一棵树,xml文件也是一棵树。

各个省市县也可以构成一颗树,淘宝京东的栏目分类也是一棵树,任何有嵌套结构的数据都可以构成一棵树。

所以,掌握树相关的算法是很有必要的。

最后附一个示例,是我实现的一个模拟windows的文件管理器,点开链接看看吧。

http://www.lizhiqianduan.com/products/ycc/examples/tree/

还没有关注订阅号的朋友,扫描二维码,或者识别图片二维码关注哦。

有最新干货会第一时间通知您哦。

image.png



打赏作者

发表评论

电子邮件地址不会被公开。 必填项已用*标注