>首页> IT >

今日热搜:详细介绍JavaScript二叉树及各种遍历算法

时间:2022-07-27 17:49:20       来源:转载
本篇文章给大家带来了关于javascript的相关知识,主要介绍了JavaScript二叉树及各种遍历算法详情,文章围绕主题展开详细的内容介绍,具有一定的参考价值,需要的小伙伴可以参考一下,希望对大家有帮助。


(资料图片仅供参考)

【相关推荐:javascript视频教程、web前端】

什么是二叉树

二叉树是每个节点最多只能有两个子节点的树,如下图所示:

一个二叉树具有以下几个特质:

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个部分,如下图:

这三个部分依次是左子树的引用,该节点包含的数据,右子树的引用,存储方式如下图所示:

与二叉树相关的算法

以下算法中遍历用到的树如下

// 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*/

广度优先遍历

实现思路如下:

创建队列,把根节点入队把对头出队并访问把队头的leftright依次入队重复执行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二叉树及各种遍历算法的详细内容,更多请关注php中文网其它相关文章!

关键词: 如下图所示 完全二叉树 深度优先