本篇文章给大家带来了关于javascript的相关知识，主要介绍了javascript二叉树及各种遍历算法详情，文章围绕主题展开详细的内容介绍，具有一定的参考价值，需要的小伙伴可以参考一下，希望对大家有帮助。
【相关推荐：javascript视频教程、web前端】
什么是二叉树
二叉树是每个节点最多只能有两个子节点的树，如下图所示：
一个二叉树具有以下几个特质：
立即学习“Java免费学习笔记（深入）”；
第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个部分，如下图：
这三个部分依次是左子树的引用，该节点包含的数据，右子树的引用，存储方式如下图所示：
与二叉树相关的算法
以下算法中遍历用到的树如下：
算家云
高效、便捷的人工智能算力服务平台
37 查看详情
// tree.jsconst bt = { val: 'A', left: { val: 'B', left: { val: 'D', left: null, right: null }, right: { val: 'E', left: null, right: null }, }, right: { val: 'C', left: { val: 'F', left: { val: 'H', left: null, right: null }, right: { val: 'I', left: null, right: null }, }, right: { val: 'G', left: null, right: null }, },}module.exports = bt
深度优先遍历
二叉树的深度优先遍历与树的深度优先遍历思路一致，思路如下：
访问根节点；访问根节点的left访问根节点的right重复执行第二三步
实现代码如下：
const bt = { val: 'A', left: { val: 'B', left: { val: 'D', left: null, right: null }, right: { val: 'E', left: null, right: null }, }, right: { val: 'C', left: { val: 'F', left: { val: 'H', left: null, right: null }, right: { val: 'I', left: null, right: null }, }, right: { val: 'G', left: null, right: null }, },}function dfs(root) { if (!root) return console.log(root.val) root.left && dfs(root.left) root.right && dfs(root.right) }dfs(bt)/** 结果A B D E C F H I G*/
广度优先遍历
实现思路如下：
创建队列，把根节点入队把对头出队并访问把队头的left和right依次入队重复执行2、3步，直到队列为空
实现代码如下：
function bfs(root) { if (!root) return const queue = [root] while (queue.length) { const node = queue.shift() console.log(node.val) node.left && queue.push(node.left) node.right && queue.push(node.right) }}bfs(bt)/** 结果A B C D E F G H I */
先序遍历
二叉树的先序遍历实现思想如下：
访问根节点;对当前节点的左子树进行先序遍历；对当前节点的右子树进行先序遍历；
如下图所示：
递归方式实现如下：
const bt = require('./tree')function preorder(root) { if (!root) return console.log(root.val) preorder(root.left) preorder(root.right)}preorder(bt)/** 结果A B D E C F H I G*/
迭代方式实现如下：
// 非递归版function preorder(root) { if (!root) return // 定义一个栈，用于存储数据 const stack = [root] while (stack.length) { const node = stack.pop() console.log(node.val) /* 由于栈存在先入后出的特性，所以需要先入右子树才能保证先出左子树 */ node.right && stack.push(node.right) node.left && stack.push(node.left) }}preorder(bt)/** 结果A B D E C F H I G*/
中序遍历
二叉树的中序遍历实现思想如下：
对当前节点的左子树进行中序遍历；访问根节点;对当前节点的右子树进行中序遍历；
如下图所示：
递归方式实现如下：
const bt = require('./tree')// 递归版function inorder(root) { if (!root) return inorder(root.left) console.log(root.val) inorder(root.right)}inorder(bt)/** 结果D B E A H F I C G*/
迭代方式实现如下：
// 非递归版function inorder(root) { if (!root) return const stack = [] // 定义一个指针 let p = root // 如果栈中有数据或者p不是null，则继续遍历 while (stack.length || p) { // 如果p存在则一致将p入栈并移动指针 while (p) { // 将 p 入栈，并以移动指针 stack.push(p) p = p.left } const node = stack.pop() console.log(node.val) p = node.right }}inorder(bt)/** 结果D B E A H F I C G*/
后序遍历
二叉树的后序遍历实现思想如下：
对当前节点的左子树进行后序遍历；对当前节点的右子树进行后序遍历；访问根节点;
如下图所示：
递归方式实现如下：
const bt = require('./tree')// 递归版function postorder(root) { if (!root) return postorder(root.left) postorder(root.right) console.log(root.val)}postorder(bt)/** 结果D E B H I F G C A*/
迭代方式实现如下：
// 非递归版function postorder(root) { if (!root) return const outputStack = [] const stack = [root] while (stack.length) { const node = stack.pop() outputStack.push(node) // 这里先入left需要保证left后出，在stack中后出，就是在outputStack栈中先出 node.left && stack.push(node.left) node.right && stack.push(node.right) } while (outputStack.length) { const node = outputStack.pop() console.log(node.val) }}postorder(bt)/** 结果D E B H I F G C A*/
【相关推荐：javascript视频教程、web前端】
以上就是详细介绍JavaScript二叉树及各种遍历算法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/548724.html
微信扫一扫 
支付宝扫一扫 
