位置: 编程技术 - 正文
JavaScript数据结构和算法之二叉树详解(javascript数据结构与算法)
编辑：rootadmin推荐整理分享JavaScript数据结构和算法之二叉树详解(javascript数据结构与算法)，希望有所帮助，仅作参考，欢迎阅读内容。
文章相关热门搜索词:javascript数据结构与算法项目计算找零,javascript数据结构与算法项目计算找零,javascript数据结构有哪些,javascript数据结构与算法项目电话号码检查器,javascript数据结构与算法第三版,javascript数据结构与算法第三版,javascript数据结构与算法 pdf,javascript数据结构,内容如对您有帮助，希望把文章链接给更多的朋友！
二叉树的概念
二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
二叉树的特点
每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。二叉树中每一个节点都是一个对象，每一个数据节点都有三个指针，分别是指向父母、左孩子和右孩子的指针。每一个节点都是通过指针相互连接的。相连指针的关系都是父子关系。
二叉树节点的定义
二叉树节点定义如下：
二叉树的五种基本形态
空二叉树只有一个根结点根结点只有左子树根结点只有右子树根结点既有左子树又有右子树
拥有三个结点的普通树只有两种情况：两层或者三层。但由于二叉树要区分左右，所以就会演变成如下的五种形态：
特殊二叉树
斜树
如上面倒数第一副图的第2、3小图所示。
满二叉树
在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。如下图所示：
完全二叉树
完全二叉树是指最后一层左边是满的，右边可能满也可能不满，然后其余层都是满的。一个深度为k，节点个数为 2^k - 1 的二叉树为满二叉树（完全二叉树）。就是一棵树，深度为k，并且没有空位。
完全二叉树的特点有：
叶子结点只能出现在最下两层。
最下层的叶子一定集中在左部连续位置。
倒数第二层，若有叶子结点，一定都在右部连续位置。
如果结点度为1，则该结点只有左孩子。
同样结点树的二叉树，完全二叉树的深度最小。
注意：满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。
算法如下：
二叉树的性质
二叉树的性质一：在二叉树的第i层上至多有2^(i-1)个结点(i>=1)
二叉树的性质二：深度为k的二叉树至多有2^k-1个结点(k>=1)
二叉树的顺序存储结构
二叉树的顺序存储结构就是用一维数组存储二叉树中的各个结点，并且结点的存储位置能体现结点之间的逻辑关系。
二叉链表
既然顺序存储方式的适用性不强，那么我们就要考虑链式存储结构啦。二叉树的存储按照国际惯例来说一般也是采用链式存储结构的。
二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。
二叉树的遍历
二叉树的遍历(traversing binary tree)是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。
二叉树的遍历有三种方式，如下：
（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。
（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。
（3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。
前序遍历：
若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。
遍历的顺序为：A B D H I E J C F K G
中序遍历：
若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。
遍历的顺序为：H D I B E J A F K C G
后序遍历：
若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点。
遍历的顺序为：H I D J E B K F G C A
实现二叉查找树
二叉查找树（BST）由节点组成，所以我们定义一个Node节点对象如下：
查找最大和最小值
查找BST上的最小值和最大值非常简单，因为较小的值总是在左子节点上，在BST上查找最小值，只需遍历左子树，直到找到最后一个节点
查找最小值该方法沿着BST的左子树挨个遍历，直到遍历到BST最左的节点，该节点被定义为：这时，当前节点上保存的值就是最小值
查找最大值
在BST上查找最大值只需要遍历右子树，直到找到最后一个节点，该节点上保存的值就是最大值。
Javascript核心读书有感之表达式和运算符 表达式是javascript中的一个短语，javascript解释器会将其计算出一个结果。程序中常用量是最简单的一类表达式就是变量。变量名也是一种简单的表达式，
JavaScript中的分号插入机制详细介绍 仅在}之前、一个或多个换行之后和程序输入的结尾被插入也就是说你只能在一行、一个代码块和一段程序结束的地方省略分号。也就是说你可以写如下
JS实现的生成随机数的4个函数分享 第一种方法/**@desc:生成随机字符串*@remark:toString方法可以接收一个基数作为参数的原理，这个基数从2到封顶。如果不指定，默认基数是进制*/functiongen
上一篇：Javascript核心读书有感之类型、值和变量(javascript核心技术)
下一篇：Javascript核心读书有感之表达式和运算符(javascript的核心语言对象包括)
