关于javascript:JavaScript中的树型数据结构

5次阅读

共计 4733 个字符,预计需要花费 12 分钟才能阅读完成。

JavaScript 中的树型数据结构

实现和遍历技术

作者:Anish Kumar 译者:同学小强 起源:stackfull

Tree 是一种乏味的数据结构,它在各个领域都有宽泛的利用,例如:

  • DOM 是一种树型数据结构
  • 咱们操作系统中的目录和文件能够示意为树
  • 家族层次结构能够示意为一棵树

树有很多变体(如堆、BST 等),可用于解决与调度、图像处理、数据库等相干的问题。许多简单的问题可能看起来和树没有关系,然而实际上能够示意为一个问题。咱们还将探讨这些问题(在本系列前面的局部中),看看树是如何使看似简单的问题更容易了解和解决的。

引言

为二叉树实现一个 节点 是非常简单的。

function Node(value){
  this.value = value
  this.left = null
  this.right = null
}
// usage
const root = new Node(2)
root.left = new Node(1)
root.right = new Node(3)

因而,这几行代码将为咱们创立一个二叉树,它看起来像这样:

           2  
        /      \
       /         \
     1            3
   /   \        /    \
null  null   null   null

这很简略。当初,咱们如何应用这个呢?

遍历

让咱们从试图遍历这些连贯的树节点 (或整颗树) 开始。就像咱们能够迭代一个数组一样,如果咱们也能够“迭代”树节点就更好了。然而,树并不是像数组那样的线性数据结构,因而遍历这些数据结构的办法不止一种。咱们能够将遍历办法大抵分为以下几类:

  • 广度优先遍历
  • 深度优先遍历

广度优先搜寻 / 遍历(BFS)

在这种办法中,咱们逐层遍历树。咱们将从根开始,而后笼罩所有的子级,以及笼罩所有的二级子级,以此类推。例如,对于下面的树,遍历会失去如下后果:

2, 1, 3

上面是一个稍微简单的树的例子,使得这个更容易了解:

要实现这种模式的遍历,咱们能够应用一个队列(先进先出)数据结构。上面是整个算法的样子:

  • 初始化一个蕴含 root 的队列
  • 从队列中删除第一项
  • 将弹出项的左右子项推入队列
  • 反复步骤 2 和 3,直到队列为空

上面是这个算法实现后的样子:

function walkBFS(root){if(root === null) return

  const queue = [root]
  while(queue.length){const item = queue.shift()
      // do something
      console.log(item)

      if(item.left) queue.push(item.left)
      if(item.right) queue.push(item.right)
   }
}

咱们能够略微批改下面的算法来返回一个二维数组,其中每个外部数组代表一个蕴含元素的层级:

function walkBFS(root){if(root === null) return

  const queue = [root], ans = []

  while(queue.length){const len = queue.length, level = []
      for(let i = 0; i < len; i++){const item = queue.shift()
          level.push(item)
          if(item.left) queue.push(item.left)
          if(item.right) queue.push(item.right)
       }
       ans.push(level)
   }
  return ans
}

深度优先搜寻 / 遍历(DFS)

在 DFS 中,咱们取一个节点并持续摸索它的子节点,直到深度达到齐全耗尽。这能够通过以下办法之一来实现:

 root node -> left node -> right node // pre-order traversal
 left node -> root node -> right node // in-order traversal
 left node -> right node -> root node // post-order traversal

所有这些遍历技术都能够迭代和递归形式实现,让咱们进入实现细节:

前序遍历

上面是一颗树的前序遍历的样子:

 root node -> left node -> right node

窍门:
咱们能够应用这个简略的技巧手动地找出任何树的前序遍历: 从根节点开始遍历整个树,放弃本人在右边。

实现:
让咱们深入研究这种遍历的理论实现。递归办法 相当直观。

function walkPreOrder(root){if(root === null) return

  // do something here
  console.log(root.val)

  // recurse through child nodes
  if(root.left) walkPreOrder(root.left)
  if(root.right) walkPreOrder(root.right)
}

前序遍历的 迭代办法 与 BFS 十分类似,不同之处在于咱们应用 堆栈 而不是 队列,并且咱们首先将左边的子元素放入堆栈:

function walkPreOrder(root){if(root === null) return

  const stack = [root]
  while(stack.length){const item = stack.pop()

      // do something
      console.log(item)

      // Left child is pushed after right one, since we want to print left child first hence it must be above right child in the stack
      if(item.right) stack.push(item.right)
      if(item.left) stack.push(item.left)
   }
}

中序遍历

上面是一颗树的中序遍历的样子:

left node -> root node -> right node

窍门:
咱们能够应用这个简略的技巧手动地找出任何树的中序遍历: 在树的底部程度搁置一个平面镜像,并对所有节点进行投影。

实现:

递归:

function walkInOrder(root){if(root === null) return

  if(root.left) walkInOrder(root.left)

 // do something here
  console.log(root.val)

  if(root.right) walkInOrder(root.right)
}

迭代: 这个算法起初可能看起来有点神秘。但它相当直观的。让咱们这样来看: 在中序遍历中,最右边的子节点首先被打印,而后是根节点,而后是右节点。所以咱们首先想到的是:

const curr = root

while(curr){while(curr.left){curr = curr.left // get to leftmost child}

  console.log(curr) // print it

  curr = curr.right // now move to right child
}

在上述办法中,咱们无奈回溯,即返回到最左侧节点的父节点,所以咱们须要一个堆栈来记录它们。因而,咱们订正后的办法可能看起来如下:

const stack = []
const curr = root

while(stack.length || curr){while(curr){stack.push(curr) // keep recording the trail, to backtrack
    curr = curr.left // get to leftmost child
  }
  const leftMost = stack.pop()
  console.log(leftMost) // print it

  curr = leftMost.right // now move to right child
}

当初咱们能够应用下面的办法来制订最终的迭代算法:

function walkInOrder(root){if(root === null) return

  const stack = []
  let current = root

  while(stack.length || current){while(current){stack.push(current)
         current = current.left
      }
      const last = stack.pop()

      // do something
      console.log(last)

      current = last.right
   }
}

后序遍历

上面是一颗树的后序遍历的样子:

 left node -> right node -> root node

窍门:

对于任何树的疾速手动后序遍历:一个接一个地提取所有最右边的叶节点。

实现:

让咱们深入研究这种遍历的理论实现。

递归:

function walkPostOrder(root){if(root === null) return

  if(root.left) walkPostOrder(root.left)
  if(root.right) walkPostOrder(root.right)

  // do something here
  console.log(root.val)

}

迭代:咱们曾经有了用于前序遍历的迭代算法。咱们能够用那个吗?因为后序遍历仿佛只是前序遍历的逆序。让咱们来看看:

// PreOrder:
root -> left -> right

// Reverse of PreOrder:
right -> left -> root

// But PostOrder is:
left -> right -> root

这里有一个轻微的区别。然而咱们能够通过略微批改前序算法,而后对其进行逆序,从而失去后序后果。总体算法如下:

// record result using 
root -> right -> left

// reverse result
left -> right -> root
  • 应用与下面的迭代前序算法相似的办法,应用长期 堆栈

    • 惟一的例外是咱们应用 root-> right-> left 而不是 root-> left-> right
  • 将遍历序列记录在一个数组 后果
  • 后果 的逆序给出了后序遍历
function walkPostOrder(root){if(root === null) return []

  const tempStack = [root], result = []

  while(tempStack.length){const last = tempStack.pop()

      result.push(last)

      if(last.left) tempStack.push(last.left)
      if(last.right) tempStack.push(last.right)
    }

    return result.reverse()}

额定:JavaScript 提醒

如果咱们能够通过以下形式遍历树该多好:

 for(let node of walkPreOrder(tree) ){console.log(node)
 }

看起来真的很好,而且很容易浏览,不是吗?咱们所要做的就是应用一个 walk 函数,它会返回一个迭代器。

以下是咱们如何批改下面的 walkPreOrder 函数,使其依照下面共享的示例运行:

function* walkPreOrder(root){if(root === null) return

  const stack = [root]
  while(stack.length){const item = stack.pop()
      yield item
      if(item.right) stack.push(item.right)
      if(item.left) stack.push(item.left)
   }
}

举荐理由

本文(配有多图)介绍了树结构在 JavaScript 语言外面如何遍历,写得浅显易懂,解释了广度优先、深度优先等多种办法的实现,翻译不免有出入,欢送斧正!

原文:https://stackfull.dev/tree-da…

往期精彩

不必递归生成有限层级的树

基于 qiankun 微前端实战部署

正文完
 0