在讲二叉树之前，应该先了解数据结构中关于树的定义：树（维基百科）。其中比较重要的常用术语：节点、父节点、度、叶子。而二叉树并不是树的特殊情况，因为二叉树和树的定义并不重合，二叉树并不是树的子集。只是二叉树类似树的结构而已。二叉树的定义：二叉树。二叉树比较重要的常用术语：左子树、右子树、根节点、满二叉树、完全二叉树。这些概念比较多比较杂，需要花时间好好理解一下。
今天我要写的是用JavaScript构建满二叉树（再进一步通过二叉树，判断二叉树是否是相同的树（leetcode），或者是否是对称二叉树(leetcode)）。二叉树是数据结构与算法中非常重要的一部分，同时也是比较难理解的部分。（我也是通过慢慢理解，自己琢磨，多做笔记，多动手，渐渐消化它的。代码部分尽量讲的详细通俗一点。）
我们假设使用数组来表示二叉树的存储结构（链表也可以，这里使用数组更加方便）
使用es6构建树的节点，添加属性（val, left，right)
这一步的主要作用就是创建二叉树的节点属性。以后二叉树的节点都靠这个函数生成，生成的new Node就全都直接拿来只用。
第二步就开始创建二叉树，这一步有点抽象，需要仔细研读下代码。
通过class，创建二叉树
代码里面的含义，容我一步步解析：（es6中class的语法和constructor我就不细讲怎么使用了）
首先创建一个空数组，用来保存二叉树中所有的节点。那么肯定得先生成二叉树的节点，所以就用到for循环来创建所有节点，并存进数组当中。这里的i是数组的索引，我们的思路是通过数组的索引，找到当前索引对应的节点、当前索引所在的深度（层）、当前索引的父节点......
所以这个代码的核心就是利用二叉树中的节点只有两个分支，从而延申出的各种特性。
比如计算n(当前代码所在的层数）就是利用二叉树的特性： 当前索引和所在层级n之间的关系。这里用一张示意图来描述会更加形象一点：
索引和层级N之间的关系图
从图中不难发现，度数（层数）n和索引之间存在的关系：二叉树左侧的索引值
i = 2 ^(n - 1) - 1
这个也是构建树的关键点。既然 i = 2^(n - 1) - 1，那我们就可以反推出
该式就是通过当前元素索引计算当前元素所在层数，但是要向下取整：
即：n = Math.floor(Math.log2(i +1) + 1)
有了这个表达式，我们就可以继续计算出，当前元素所在层数的第一个索引 p:
即: p = Math.pow(2, n -1) -1
继而可以计算出当前索引对应的父节点对应的索引 q：
即: q = Math.floor((i - p) / 2) + Math.pow(2, n - 2) - 1
计算父节点的索引的时候，可能有点会迷糊，为什么要把当前位置的索引 i (p为当前层数的第一个索引）减去 p 除以 2 向下取整呢？这就和二叉树的特点又有关系了。因为二叉树中，一个节点对应两个子节点，当前位置索引减去当前层数第一个索引除以2，取整，就是为了计算出父节点相对于父节点那层的第一个索引移动的数值。Math.pow(2, n - 2) - 1这个式子则是上一层的第一索引值，也就是父节点的层数对应的第一个索引值。如果还是不明白，可以自己动手算一算，纸上得来终觉浅。
好了，有了这一步，那父节点的索引我们也就知道了。其实到这里二叉树基本已经确定完毕了，下面就是让这棵树散开枝叶了。
这里就可以开始解释，为什么要在计算n层级是，先加入一个判断 i > 0,因为当索引 i = 0时，它没有父节点，如果你没加判断条件，运行时会报错。parent.left默认初始值都是null,当遍历到node节点时，把它赋值给他的父节点的左子节点。
我们只需要一个根节点root就行了。利用根节点，就可以一层一层的遍历二叉树。最后把保存节点的临时数组的内存释放，返回跟节点，二叉树的构建到此就结束了。当然，你传入一个数组进去，会输出一个对象node，就是数组的头元素，val等于当前元素的值，left，right都是一个对象，left是左节点，里面有左节点的属性，right是有节点，里面有右节点的属性，同时这些属性都是嵌套的，因为我们就是用这种方式构建二叉树的。
我传入的数组是[3,9,20,null,null,15,7]
对应的树的结构：（先序遍历）
[3,9,20,null,null,15,7]
如果你想验证对称二叉树，就需要在里面定义一个方法，判断二叉树是否对称。如果有人看这篇文章的话， 我再写吧。。。。。。估计也就我看看而已，哈哈哈
后面有时间了，再写下二叉树的遍历: 先序遍历（波兰式），中序遍历，后序遍历（逆波兰）
网友评论