JavaScript二叉树及遍历算法实例分析

这篇“JavaScript二叉树及遍历算法实例分析”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“JavaScript二叉树及遍历算法实例分析”文章吧。二叉树是每个节点最多只能有两个子节点的树，如下图所示：一个二叉树具有以下几个特质：第i层的节点最有只有2^(i-1)个；如果这颗二叉树的深度为k，那二叉树最多有2^k-1个节点；在一个非空的二叉树中，若使用n0表示叶子节点的个数，n2是度为2的非叶子节点的个数，那么两者满足关系n0 = n2 + 1。如果在一个二叉树中，除了叶子节点，其余的节点的每个度都是2，则说明该二叉树是一个满二叉树，如下图所示：满二叉树除了满足普通二叉树特质，还具有如下几个特质：满二叉树的的第n层具有2^(n-1)个节点；深度为k的满二叉树一定存在2^k-1个节点，叶子节点的个数为2^(k-1)；具有n个节点的满二叉树的深度为log_2^(n+1)。如果一个二叉树去掉最后一次层是满免费云主机、域名二叉树，且最后一次的节点是依次从左到右分布的，则这个二叉树是一个完全二叉树，如下图所示：存储二叉树的常见方式分为两种，一种是使用数组存储，另一种使用链表存储。使用数组存储二叉树，如果遇到完全二叉树，存储顺序从上到下，从左到右，如下图所示：如果是一个非完全二叉树，如下图所示：需要先将其转换为完全二叉树，然后在进行存储，如下图所示：可以很明显的看到存储空间的浪费。使用链表存储通常将二叉树中的分为3个部分，如下图：这三个部分依次是左子树的引用，该节点包含的数据，右子树的引用，存储方式如下图所示：以下算法中遍历用到的树如下：二叉树的深度优先遍历与树的深度优先遍历思路一致，思路如下：访问根节点；访问根节点的left访问根节点的right重复执行第二三步实现代码如下：实现思路如下：创建队列，把根节点入队把对头出队并访问把队头的left和right依次入队重复执行2、3步，直到队列为空实现代码如下：二叉树的先序遍历实现思想如下：访问根节点;对当前节点的左子树进行先序遍历；对当前节点的右子树进行先序遍历；如下图所示：递归方式实现如下：迭代方式实现如下：二叉树的中序遍历实现思想如下：对当前节点的左子树进行中序遍历；访问根节点;对当前节点的右子树进行中序遍历；如下图所示：递归方式实现如下：迭代方式实现如下：二叉树的后序遍历实现思想如下：对当前节点的左子树进行后序遍历；对当前节点的右子树进行后序遍历；访问根节点;如下图所示：递归方式实现如下：迭代方式实现如下：以上就是关于“JavaScript二叉树及遍历算法实例分析”这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注云技术行业资讯频道。

相关推荐: node是不是免费的

本文小编为大家详细介绍“node是不是免费的”，内容详细，步骤清晰，细节处理妥当，希望这篇“node是不是免费的”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。 免费云主机、域名node是免费的；node发布于2009年5月，由Rya…