二叉树二叉树（BinaryTree）是一种树结构，其特点是每个节点最多有两个分支节点，一棵二叉树通常由一个根节点组成，一个分支节点，由叶节点组成。每个分支节点通常称为子树。根节点：二叉树的最顶层节点分支节点：除了根节点，它还有叶子节点叶子节点：除了自己之外没有其他子节点。2是6和3的父节点，反之6和3是2个子节点。二叉树的三个性质在二叉树的第i层，当i=1时，最多有2^i-1个节点，只有一个根节点，2^(i-1)=2^0=1一棵深度为k的二叉树，当i=2时最多有2^k-1个节点，2^k-1=2^2-1=3个节点对于任意一棵二叉树T，如果汇总点数为n0，度数为2（子树数为2）的节点数为n2，则n0=n2+1树和二叉树的三个主要差分树的节点数至少为1，而二叉树树中的节点个数可以为0。树中节点的最大度（节点个数）没有限制，而二叉树中节点的最大度为2.完全二叉树（completebinarytree）和满二叉树（fullbinarytree）满二叉树：深度为k，节点数为2^k-1的二叉树称为满二叉树完全二叉树：完全二叉树tree的意思是左边最后一层是Full，右边可能是full也可能不是，那么剩下的二叉树就叫做完全二叉树（fullbinarytree也是完全二叉树）。二叉树的数组表示，用数组来表示二叉树的结构，一组数组从根结点开始，从上到下，从左到右，依次填充成一棵完整的二叉树，如图以下。通过上图，我们可以分析出一个数组表示的完整二叉树，其属性如下：left=index*2+1，例如：根节点的下标为0，则左节点的值为下标array[0*2+1]=1right=index*2+2，例如：根节点的下标为0，则右节点的值为下标array[0*2+2]=2序数>=floor(N/2)都是叶子节点，例如：floor(9/2)=4，那么下标4开始的值都是叶子节点NodeBinaryHeap二叉堆用a表示完全二叉树，用数组表示，但是二叉堆需要满足以下性质：二叉堆的父节点的key值总是大于等于（小于等于）任意一个的key值子节点当父节点的键值大于或等于（小于或等于）其每个子节点的键值时，称为最大堆（minimumheap）。从上图可以看出：左图：父节点总是大于等于它的子节点，所以满足二叉堆的性质。右图：分支节点7作为2和12的父节点不满足其性质（大于或等于子节点）二叉堆的主要操作insert：插入节点delete：删除节点max-hepify：调整分支节点堆属性rebuildHeap：重建整个二叉堆sort：sort从上面的简单介绍初始化一个二叉堆，我们可以知道二叉堆的初始化很简单，就是一个数组来初始化一个保存数组长度的数组结构classHeap{constructor(arr){this.data=[...arr];这个.size=这个。数据长度；}}max-heapify最大堆操作max-heapify是调整每个不满足最大堆属性的分支节点的操作。如上图：调整分支节点2（分支节点2不满足最大堆的性质）默认，分支节点为最大值将2与左右分支进行比较，从2、12、12、5、再根据上面提到的二叉堆的性质与2交换位置，得到分支节点2的左节点和右节点，并比较三个节点，得到最大值的下标max。如果节点本身是最大值，则停止运算，将max节点与父节点进行比较。交换并重复step2的操作，从2、4、7中找出最大值递归地与2交换maxHeapify(i){letmax=i;如果（我>=this.size）{返回；}//当前序号的左节点constl=i*2+1;//当前需要的右节点constr=i*2+2;//求当前节点及其左右节点中的最大值if(lthis.data[max]){max=l;}if(rthis.data[max]){max=r;}//final如果最大节点是自己，则已经满足最大堆属性，停止操作if(max===i){return;}//父节点和最大值节点之间的交换constt=this.data[i];this.data[i]=this.data[max];这个.data[max]=t;//继续递归执行returnthis.maxHeapify(max);}重构堆我们可以看到，新初始化的堆由一个数组组成，表明此时可能不满足最大堆或最小堆的性质，这时候我们可能需要把整个堆建成我们想要的样子。上面我们做了max-heapify的操作，max-heapify只是调整了某个分支节点。要将整个堆构建成最大堆，需要对所有分支节点进行一次max-heapify操作，如下图，我们需要对12、3、2、4个分支节点进行max-heapify操作依次15具体步骤：找到所有分支节点：上面说的堆的性质叶子节点的序号>=Math.floor(n/2)，所以序号小于Math.floor(n/2)是我们需要调整的节点。比如途中显示的数组是[15,2,3,12,5,2,8,4,7]=>Math.floor(9/2)=4=>index小于4的就是15，分别为2、3、12（待调整节点）、5、2、8、4、7为叶节点。对找到的所有节点进行maxHeapify操作rebuildHeap(){//叶子节点constL=Math.floor(this.size/2);for(leti=L-1;i>=0;i--){这个,maxHeapify(i);}}最大堆排序最大堆的排序，如上图所示：交换首末位置取出堆中的最后一个元素，相当于堆的size-1，然后执行amax-heapify操作重复以上三步，直到size=0（我们已经在max-heapify函数中做了这个边界条件）sort(){for(leti=this.size-1;i>0;i--){交换(this.data,0,i);这个.size--;这个.maxHeapify(0);}}插入和删除这个的插入和删除比较简单，就是对一个数组进行插入和删除操作，插入最后的堆长度+1，判断插入后是否还是最大堆。如果不是，重建堆insert(key){this.data[this.size]=key;this.size++if(this.isHeap()){返回；}this.rebuildHeap();}删除数组中的一个元素Heaplength-1判断是否为堆如果不是则重建堆delete(index){if(index>=this.size){return;}这个.data.splice(index,1);这个.size--;如果(this.isHeap()){返回;}this.rebuildHeap();}完整代码/***最大堆*/functionleft(i){returni*2+1;}functionright(i){returni*2+2;}functionswap(A,i,j){constt=A[i];A[i]=A[j];A[j]=t;}classHeap{constructor(arr){this.data=[...arr];this.size=this.data.length;}/***重组堆*/rebuildHeap(){constL=Math.floor(this.size/2);for(leti=L-1;i>=0;i--){this.maxHeapify(i);}}isHeap(){constL=Math.floor(this.size/2);for(leti=L-1;i>=0;i++){constl=this.data[left(i)]||Number.MIN_SAFE_INTEGER;constr=this.data[右(i)]||Number.MIN_SAFE_INTEGER;constmax=Math.max(this.data[i],l,r);if(max!==this.data[i]){返回false;}返回真；}}sort(){for(leti=this.size-1;i>0;i--){swap(this.data,0,i);这个.size--;这个.maxHeapify(0);}}insert(key){this.data[this.size++]=key;如果(this.isHeap()){返回;}this.rebuildHeap();}删除（索引）{如果（索引>=this.size){返回;}this.data.splice(index,1);这个.size--;如果(this.isHeap()){返回;}this.rebuildHeap();}/***Heap所有其他地方满足属性*只有根节点，重构堆属性*@param{*}i*/maxHeapify(i){letmax=i;如果(i>=this.size){返回;}//求左右节点序号较大的一个constl=left(i);constr=右(i);if(lthis.data[max]){max=l;}if(rthis.data[max]){max=r;}//如果当前节点最大，则已经是最大堆if(max===i){return;}swap(this.data,i,max);//继续递归执行returnthis.maxHeapify(max);}}module.exports=堆；总结堆到这里就结束了，堆在二叉树中比较简单，常用于排序和优先级队列。堆的核心是max-heapify操作和堆的三个属性。下一篇应该介绍一下二叉搜索树。欢迎大家指出文章中的错误，有什么写作建议也可以提出。我会继续写一些关于前端的技术文章。喜欢的话可以关注一禾，给个赞。你的喜欢是我写作的动力。对了，我在等第一个粉丝哈哈。以下个人公众号，欢迎大家关注，用户量达到一定数量，我会放出一些前端教学视频
