亲宝软件园·资讯

展开

JavaScript实现树结构(一)

AhuntSun 人气:0
## JavaScript实现树结构(一) ### 一、树结构简介 #### 1.1.简单了解树结构 **什么是树?** 真实的树: ![image-20200229205530929](https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%A0%91%E4%B8%80/1.png) **树的特点:** * 树一般都有一个**根**,连接着根的是**树干**; * 树干会发生分叉,形成许多**树枝**,树枝会继续分化成更小的**树枝**; * 树枝的最后是**叶子**; 现实生活中很多结构都是树的抽象,模拟的树结构相当于旋转`180°`的树。 ![image-20200229205630945](https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%A0%91%E4%B8%80/2.png) **树结构对比于数组/链表/哈希表有哪些优势呢:** **数组:** * 优点:可以通过**下标值访问**,效率高; * 缺点:查找数据时需要先对数据进行**排序**,生成**有序数组**,才能提高查找效率;并且在插入和删除元素时,需要大量的**位移操作**; **链表:** * 优点:数据的插入和删除操作效率都很高; * 缺点:**查找**效率低,需要从头开始依次查找,直到找到目标数据为止;当需要在链表中间位置插入或删除数据时,插入或删除的效率都不高。 **哈希表:** * 优点:哈希表的插入/查询/删除效率都非常高; * 缺点:**空间利用率不高**,底层使用的数组中很多单元没有被利用;并且哈希表中的元素是**无序**的,不能按照固定顺序遍历哈希表中的元素;而且不能快速找出哈希表中**最大值或最小值**这些特殊值。 **树结构:** 优点:树结构综合了上述三种结构的优点,同时也弥补了它们存在的缺点(虽然效率不一定都比它们高),比如树结构中数据都是有序的,查找效率高;空间利用率高;并且可以快速获取最大值和最小值等。 总的来说:**每种数据结构都有自己特定的应用场景** **树结构:** * **树(Tree)**:由 n(n ≥ 0)个节点构成的**有限集合**。当 n = 0 时,称为**空树**。 对于任一棵非空树(n > 0),它具备以下性质: * 数中有一个称为**根(Root)**的特殊节点,用 **r **表示; * 其余节点可分为 m(m > 0)个互不相交的有限集合 T~1~,T~2~,...,T~m~,其中每个集合本身又是一棵树,称为原来树的**子树(SubTree)**。 **树的常用术语:** ![image-20200229221126468](https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%A0%91%E4%B8%80/3.png) * **节点的度(Degree)**:节点的**子树个数**,比如节点B的度为2; * **树的度**:树的所有节点中**最大的度数**,如上图树的度为2; * **叶节点(Leaf)**:**度为0的节点**(也称为叶子节点),如上图的H,I等; * **父节点(Parent)**:度不为0的节点称为父节点,如上图节点B是节点D和E的父节点; * **子节点(Child)**:若B是D的父节点,那么D就是B的子节点; * **兄弟节点(Sibling)**:具有同一父节点的各节点彼此是兄弟节点,比如上图的B和C,D和E互为兄弟节点; * **路径和路径长度**:路径指的是一个节点到另一节点的通道,路径所包含边的个数称为路径长度,比如A->H的路径长度为3; * **节点的层次(Level)**:规定**根节点在1层**,其他任一节点的层数是其父节点的**层数加1**。如B和C节点的层次为2; * **树的深度(Depth)**:树种所有节点中的**最大层次**是这棵树的深度,如上图树的深度为4; #### 1.2.树结构的表示方式 * **最普通的表示方法**: ![image-20200229230417613](https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%A0%91%E4%B8%80/4.png) 如图,树结构的组成方式类似于链表,都是由一个个节点连接构成。不过,根据每个父节点子节点数量的不同,每一个父节点需要的引用数量也不同。比如节点A需要3个引用,分别指向子节点B,C,D;B节点需要2个引用,分别指向子节点E和F;K节点由于没有子节点,所以不需要引用。 这种方法缺点在于我们无法确定某一结点的引用数。 * **儿子-兄弟表示法**: ![image-20200229232805477](https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%A0%91%E4%B8%80/5.png) 这种表示方法可以完整地记录每个节点的数据,比如: ``` //节点A Node{ //存储数据 this.data = data //统一只记录左边的子节点 this.leftChild = B //统一只记录右边的第一个兄弟节点 this.rightSibling = null } //节点B Node{ this.data = data this.leftChild = E this.rightSibling = C } //节点F Node{ this.data = data this.leftChild = null this.rightSibling = null } ``` 这种表示法的优点在于每一个节点中引用的数量都是确定的。 * **儿子-兄弟表示法旋转** 以下为儿子-兄弟表示法组成的树结构: ![image-20200229234549049](https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%A0%91%E4%B8%80/6.png) 将其顺时针旋转45°之后: ![image-20200229235549522](https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%A0%91%E4%B8%80/7.png) 这样就成为了一棵**二叉树**,由此我们可以得出结论:**任何树都可以通过二叉树进行模拟**。但是这样父节点不是变了吗?其实,父节点的设置只是为了方便指向子节点,在代码实现中谁是父节点并没有关系,只要能正确找到对应节点即可。 ### 二、二叉树 #### 2.1.二叉树简介 **二叉树的概念**:如果树中的每一个节点最多只能由**两个子节点**,这样的树就称为**二叉树**; 二叉树十分重要,不仅仅是因为简单,更是因为几乎所有的树都可以表示成二叉树形式。 **二叉树的组成**: * 二叉树可以为空,也就是没有节点; * 若二叉树不为空,则它由根节点和称为其左子树TL和右子树TR的两个不相交的二叉树组成; **二叉树的五种形态**: ![image-20200301001718079](https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%A0%91%E4%B8%80/8.png) 上图分别表示:空的二叉树、只有一个节点的二叉树、只有左子树TL的二叉树、只有右子树TR的二叉树和有左右两个子树的二叉树。 **二叉树的特性**: * 一个二叉树的第 i 层的最大节点树为:2^(i-1)^,i >= 1; * 深度为k的二叉树的最大节点总数为:2^k^ - 1 ,k >= 1; * 对任何非空二叉树,若 n~0~ 表示叶子节点的个数,n~2~表示度为2的非叶子节点个数,那么两者满足关系:n~0~ = n~2~ + 1;如下图所示:H,E,I,J,G为叶子节点,总数为5;A,B,C,F为度为2的非叶子节点,总数为4;满足n~0~ = n~2~ + 1的规律。 ![image-20200301092140211](https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%A0%91%E4%B8%80/9.png) #### 2.2.特殊的二叉树 **完美二叉树** 完美二叉树(Perfect Binary Tree)也成为满二叉树(Full Binary Tree),在二叉树中,除了最下一层的叶子节点外,每层节点都有2个子节点,这就构成了完美二叉树。 ![image-20200301093237681](https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%A0%91%E4%B8%80/10.png) **完全二叉树** 完全二叉树(Complete Binary Tree): * 除了二叉树最后一层外,其他各层的节点数都达到了最大值; * 并且,最后一层的叶子节点从左向右是连续存在,只缺失右侧若干叶子节点; * 完美二叉树是特殊的完全二叉树; ![image-20200301093659373](https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%A0%91%E4%B8%80/11.png) 在上图中,由于H缺失了右子节点,所以它不是完全二叉树。 #### 2.3.二叉树的数据存储 常见的二叉树存储方式为**数组**和**链表**: **使用数组:** * **完全二叉树**:按从上到下,从左到右的方式存储数据。 ![image-20200301094919588](https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%A0%91%E4%B8%80/12.png) | 节点 | A | B | C | D | E | F | G | H | | -------- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | | **序号** | **1** | **2** | **3** | **4** | **5** | **6** | **7** | **8** | 使用数组存储时,取数据的时候也十分方便:左子节点的序号等于父节点序号 * 2,右子节点的序号等于父节点序号 * 2 + 1 。 * **非完全二叉树**:非完全二叉树需要转换成完全二叉树才能按照上面的方案存储,这样会浪费很大的存储空间。 ![image-20200301100043636](https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%A0%91%E4%B8%80/13.png) | 节点 | A | B | C | ^ | ^ | F | ^ | ^ | ^ | ^ | ^ | ^ | M | | -------- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ------ | ------ | ------ | ------ | | **序号** | **1** | **2** | **3** | **4** | **5** | **6** | **7** | **8** | **9** | **10** | **11** | **12** | **13** | **使用链表** 二叉树最常见的存储方式为**链表**:每一个节点封装成一个Node,Node中包含存储的数据、左节点的引用和右节点的引用。 ![image-20200301100616105](https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%A0%91%E4%B8%80/14.png) ### 三、二叉搜索树 #### 3.1.认识二叉搜索树 **二叉搜索树**(**BST**,Binary Search Tree),也称为**二叉排序树**和**二叉查找树**。 二叉搜索树是一棵二叉树,可以为空; 如果不为空,则满足以下**性质**: * 条件1:非空左子树的**所有**键值**小于**其根节点的键值。比如三中节点6的所有非空左子树的键值都小于6; * 条件2:非空右子树的**所有**键值**大于**其根节点的键值;比如三中节点6的所有非空右子树的键值都大于6; * 条件3:左、右子树本身也都是二叉搜索树; ![image-20200301103139916](https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%A0%91%E4%B8%80/15.png) 如上图所示,树二和树三符合3个条件属于二叉树,树一不满足条件3所以不是二叉树。 **总结:**二叉搜索树的特点主要是**较小的值**总是保存在**左节点**上,相对**较大的值**总是保存在**右节点**上。这种特点使得二叉搜索树的查询效率非常高,这也就是二叉搜索树中"搜索"的来源。 #### 3.2.二叉搜索树应用举例 下面是一个二叉搜索树: ![image-20200301111718686](https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%A0%91%E4%B8%80/16.png) 若想在其中查找数据10,只需要查找4次,查找效率非常高。 * 第1次:将10与根节点9进行比较,由于10 > 9,所以10下一步与根节点9的右子节点13比较; * 第2次:由于10 < 13,所以10下一步与父节点13的左子节点11比较; * 第3次:由于10 < 11,所以10下一步与父节点11的左子节点10比较; * 第4次:由于10 = 10,最终查找到数据10 。 ![image-20200301111751041](https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%A0%91%E4%B8%80/17.png)同样是15个数据,在排序好的数组中查询数据10,需要查询10次: ![image-20200301115348138](https://gitee.com/ahuntsun/BlogImgs/raw/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%A0%91%E4%B8%80/18.png) 其实:如果是排序好的数组,可以通过二分查找:第一次找9,第二次找13,第三次找15...。我们发现如果把每次二分的数据拿出来以树的形式表示的话就是**二叉搜索树**。这就是数组二分法查找效率之所以高的原因。 > 参考资料:[JavaScript数据结构与算法](https://www.bilibili.com/video/av86801505?from=search&seid=4967761411915016256)

加载全部内容

相关教程
猜你喜欢
用户评论