【JavaScript】数据结构之树

什么是树形结构？

• 一种分层数据的抽象模型，用来分层级关系的。
• 虚拟dom它所组织的那个数据原理就是树形结构

深度优先搜索（遍历）- 递归

• 从根出发，尽可能深的搜索树的节点
• 技巧
  • 访问根节点
  • 对根节点的children挨个进行深度优化搜索

广度优先搜索（遍历）

• 从根出发，优先访问离根节点最近的节点
• 技巧
  • 新建一个队列，把根节点入队
  • 把队头出队
  • 把队头的children挨个入队
  • 重复上面二三步骤，直到队列为空为止

树 - 多叉树

• dom结构是典型的多叉树
  

树 - 二叉树

• 前序遍历 & 先序遍历
  • 规则：根 左 右
  • 先从根出发 > 拿左子树的左 > 拿左子树的右，等左边都结束 > 再拿右子树的左 > 拿右子树的右
  • 可以通过递归算法实现，也可以通过迭代算法（栈）实现。
• 中序遍历
  • 规则：左 根 右