之前已经介绍过数据结构：栈、队列、链表、集合。如果想了解上一篇，可以看我之前的文章。传送门如下：前端算法系列一：时间复杂度、空间复杂度，以及数据结构栈、队列的实现前端算法系列二：数据结构链表、双向链表、闭环链表、有序链表罗列前端算法系列三：数据结构数据集前面的学习和理解已经理解并掌握了部分数据结构知识，但是我们前面提到的，不管是栈，队列，还是集合链表，实际上都是比较简单的数据结构。我们在用js的时候，用一个Arrays或者nativeAPIs就可以满足这种结构，所以比较容易理解。今天我们要学习的是数据结构中比较复杂的——树；树：树是分层数据的抽象模型。现实生活中最常见的树的例子是家谱，从根节点开始向两边延伸。在我们实际编程中，经常会用到这种数据结构，例如：我们页面的DOM树，vue的组件树，ast的抽象语法树等等，树的特点是什么？通过下图可以理解树是由一系列具有父子关系的节点组成的。每个节点都有一个父节点（根节点除外）和零个或多个子节点。这一系列节点的顶点处的节点是根节点。根节点该节点是树的开始。它没有父节点，树中的每个元素都是一个节点；那些没有子节点的成为叶节点或外部节点。一棵树的高度取决于所有节点的最大深度值（高度在平衡二叉树中会有用）。二叉树二叉树中的一个节点最多可以有两个孩子：一个是左孩子，另一个是右孩子。上图是一棵二叉树，每个节点最多有两个子节点，分别是左节点和右节点。BinarySearchTreeBinarySearchTree(BST)是二叉树的一种，但严格要求左子节点小于父节点，右子节点大于父节点。实现二叉搜索树类。二叉查找树中的每一个元素都是一个节点，实现节点Node类的构造。该节点有一个值及其左子节点和右子节点。导出类TreeNode{constructor(key){this.key=key;this.left=null;this.right=null;}}类似于链表，节点之间的关系用指针表示。在双向链表中，每个节点包含两个指针，一个指向下一个节点，另一个指向前一个节点。对于树，使用相同的方法（也使用两个指针），但一个指向左孩子，另一个指向右孩子。因此，将声明一个Node类来表示树中的每个节点。接下来我们实现一个树类：import{defaultCompare,COMPARE}from"../util";import{TreeNode}from"./TreeNode";exportdefaultclassBinarySearchTree{constructor(compareFn=defaultCompare){this.compareFn=compareFn;this.root=null;}}在类中初始化根节点root=null，并设置一个比较函数，用于在插入和查找键值时比较大小。首先定义二叉树中的一些API：insert（插入）、search（搜索）、inOrderTraverse（中序）、prevOrderTraverse（前序）、postOrderTraverse（后序）、min（最小值）、max（最大值）、remove（删除）.接下来，我们将一一讲解如何实现这些api方法。1.insert(key)：向树中插入一个新的key。insert(key){if(!this.root){this.root=newTreeNode(key);}else{this.insertNode(this.root,key);}}insertNode(node,key){if(this.compareFn(key,node.key)===COMPARE.LESS_THAN){constleftNode=node.left;if(!leftNode){node.left=newTreeNode(key);}else{this.insertNode(leftNode,key);}}else{constrightNode=node.right;if(!rightNode){node.right=newTreeNode(key);}else{this.insertNode(rightNode,key);}}}插入（键）；在中插入一个值为key的元素，步骤如下：1.插入时，会先判断该数是否有根节点。如果没有根节点，那么插入的元素将被赋予根节点；2.如果有根节点node，将根节点root作为value和key一起传给insertNode(node,key)；3.insertNode方法首先将节点的key和传入的key进行比较，如果传入的key较小（较大），则判断该节点的左（右）子节点。如果左（右）子节点不存在，则新插入的关键节点为该节点的左（右）子节点。4.否则，以左（右）子节点为结点，递归调用insertNode，重复上述2、3步。测试代码：实现构建二叉搜索树；consttree=newBinarySearchTree();树.插入（11）；树.插入（7）；树.插入（15）；树.插入（5）；tree.insert(3);tree.insert(9);tree.insert(8);tree.insert(10);tree.insert(13);tree.insert(12);tree.insert(14);tree.insert(20);tree.insert(18);tree.insert(25);测试结果如下图所示：在这棵二叉搜索树中插入6，tree.insert(6)，插入过程如图在下图中；2.search(key)：在树中查找一个key。如果节点存在则返回true，否则返回false。在树中查找某个节点元素时，从根节点开始查找遍历。如果找到该元素，则返回true，如果未找到，则返回false。将根节点和key作为参数传入，然后将根节点值与传入的key值进行比较；2.如果key值小（大），则将传入节点的左（右）节点与key值之和传递给searchNode进行递归调用；3、此时searchNode会将传入的节点的值与key值进行比较；4、如果相等，则返回true并停止查找，否则重复2、3步，直到遍历完整个粒子树，最后仍未找到则返回false；search(key){returnthis.searchNode(this.root,key);}searchNode(node,key){if(node){if(this.compareFn(key,node.key)===COMPARE.LESS_THAN){返回this.searchNode(node.left,key);}elseif(this.compareFn(key,node.key)===COMPARE.BIGGER_THAN){returnthis.searchNode(node.right,key);}else{返回真；}}returnfalse;}测试代码：tree.search(5);//truetree.search(55);//true总结：从二叉树搜索我们可以发现，如果树分布是均匀的（即平衡二叉树后面会提到），那么查找的时候永远是二分查找。这种搜索方式的时间复杂度是O(n):log2n。二叉树的遍历需要遍历一棵二叉树的所有元素节点。通常有三种方法：中序遍历、前序遍历和后序遍历。下面我们就来看看这三种遍历方法是如何实现的。1.中序遍历中序遍历的特点是如果节点有左子树，则先向左遍历，直到左节点为null，回溯访问该节点，再访问右子树结点直到遍历完整的树，对于二叉搜索树来说，这次遍历的结果是从小到大排序的（因为二叉搜索树严格按照左孩子节点小于父节点，右孩子节点大于父节点），实现代码如下：//inOrderTraverse(callback){this.inOrderTraverseNode(this.root,callback);}inOrderTraverseNode(node,callback){if(node){this.inOrderTraverseNode(node.left,回调);回调（节点键）；this.inOrderTraverseNode(node.right,callback);}}测试代码：letarr=[];tree.inOrderTraverse((key)=>arr.push(key));控制台日志（arr）；//[3,5,7,8,9,10,11,12,13,14,15,18,20,25]inOrderTraverse((val)=>{arr.push(val)});调用这个方法的时候，会调用inOrderTraverseNode方法，传入根节点，然后递归左子树。递归完成后回溯访问node节点，然后递归该节点的右子树，直到遍历完整树。过程如下：2.前序前序遍历与中序遍历的区别在于，前序遍历先访问本节点的key值然后递归遍历左子树，再递归遍历右子树，直到遍历完整树；代码实现如下this.prevOrderTraverseNode(node.left,callback);这个.prevOrderTraverseNode(node.right,callback);}}测试代码：letarr=[];tree.prevOrderTraverse((key)=>arr.push(key));console.log(arr);//[11,7,5,3,9,8,10,15,13,12,14,20,18,25]3.后序遍历后序遍历是为了先访问节点的后代节点，再访问节点本身实现代码如下：//postorderpostOrderTraverse(callback){this.postOrderTraverseNode(this.root,callback);}postOrderTraverseNode(node,callback){if(node){this.postOrderTraverseNode(node.left,callback);这。postOrderTraverseNode(node.right,callback);回调（节点键）；}}测试代码：letarr=[];tree.postOrderTraverse((key)=>arr.push(key));console.log(arr);//[3,5,8,10,9,7,12,14,13,18,25,20,15,11]后序遍历过程如图下图：4.min(),max()returntree在二叉搜索树中找到最小\最大值的最小节点。通过二叉搜索树的特性，我们知道树的左（右）子节点比父节点小（大），左（右）子树也满足这个条件，所以最左（右）子树整棵树的子节点为最小值，实现代码如下：//最小值min(){returnthis.minNode(this.root);}minNode(node){while(node&&node.left){节点=node.left;}returnnode;}//最大值max(){returnthis.maxNode(this.root);}maxNode(node){while(node&&node.right){node=node.right;}returnnode;}5.remove(key):从树中移除一个key。remove(key){this.root=this.removeNode(this.root,key);}removeNode(node,key){if(!node){返回空；}if(this.compareFn(key,node.key)===COMPARE.LESS_THAN){node.left=this.removeNode(node.left,key);返回节点；}elseif(this.compareFn(key,node.key)===COMPARE.BIGGER_THAN){节点。right=this.removeNode(node.right,key);返回节点；}else{if(!node.left&&!node.right){node=null;返回节点；}if(!node.left){node=node.right;返回节点；}if(!node.right){node=node.left;返回节点；}让minNode=this.minNode(node.right);node.key=minNode.key;node.right=this.removeNode(node.right,minNode.key);返回节点；}}二叉搜索树中删除节点处理起来比较复杂：删除节点分为三种情况：1.删除节点为Leaf节点（即没有左右子节点）；2、删除的节点有左子节点或右子节点；3、删除的子节点既有左子节点也有右子节点，这三种情况分别处理。下面分别讨论这三种情况；1、删除的节点没有左右子节点；这种情况最简单，因为没有子节点，我们只需要找到该节点，将其父节点指向它的指针设置为Deleted，因为null，就轻松愉快的完成了。`if(!node.left&&!node.right){node=null;返回节点；}`在代码中，我们直接将找到的叶子节点赋值为null并返回，其实就是相对于其父节点的指针赋值为null；例如，tree.remove(3)；先找到节点3，然后置为null，返回给父节点；2、删除的节点有左子节点或右子节点；这种情况比较简单。如果删除的节点没有左子节点，则将其右子节点赋值给自己，并返回。同样，如果没有右子节点，则将左子节点赋给自己。本身，然后返回；如果（！node.left）{node=node.right;返回节点;}if(!node.right){node=node.left;returnnode;}代码中的实现是如果有右孩子可以用右孩子节点自己替换，如果有左孩子节点就用左孩子节点替换自己；例如：tree.remove(5)；从上图我们可以看出，首先在树中找到节点5，然后把节点5替换为它的左子节点3，这样节点7的左子节点直接指向节点3，并删除元素5。单独有一个右子节点的情况与此类似。3、删除的子节点既有左子节点又有右子节点；这种情况比前两种更复杂。也是1.先找到节点，再2.找到右子树3.同时右子树也要删除最小值，作为删除节点的右子节点。让minNode=this.minNode(node.right);node.key=minNode.key;node.right=this.removeNode(node.right,minNode.key);例如：tree.remove(15);总结到目前为止我们简单介绍了二叉搜索树的一些特性和它的api，学习了如何插入和删除节点以及遍历树的三种方式。看起来很完美，但实际上，这些只是理想状态，比如我们举的这棵树就非常理想了，两侧是平衡的。如果我们插入一个有序数，或者我们刚插入的根节点是一个小数或一个大数，结果后面插入的元素都偏移到根节点的一侧，所以它不是一棵平衡树，而且很多它的特性会退化。比如刚才插入了一个有序数，那么树就会退化为链表，形成一个链表而不是树。这就引入了一种重要的树，平衡二叉树（AVLTree）。平衡二叉树每次插入时都会调整树的结构，保证树的两侧深度之差的绝对值小于等于1。平衡二叉树和红黑树稍后补充，今天就到此为止，感谢阅读，如有错误请及时指正。最后：更多信息请看：源码或搜索公众号：非著名bug验证者
