目录树，背后的故事

2017-12-11 本文已影响38人亨利何

何宏伟

从自然抽象

[嵌牛导读]

最近项目中使用了一种树型控件

Tree Directory

这种树形控件被使用在这样的场景：

项目中单个配置需要多个子级配置完成后才可以生成
单个配置所涵盖的信息属于树形结构，类似于“n叉树”

这种树形控件，其展示方式采用级联层次的树形方式，简单易懂，层次分明，配置明确。我们的身边这种树形目录太多太多，像书本的目录，word文档的目录，一篇论文的目录，包括HTML页面层层叠叠的节点等等，所以我们有必要近距离看看这棵树。

[嵌牛鼻子]

BFS，DFS，二叉树，N叉树

[嵌牛提问]

二叉树是在接触数据结构，算法过程中一定会遇见的，如何从树顶到树底彻底的访问树的每一个节点？
将二叉树扩展到n叉树，有什么不同吗？

[嵌牛正文]

1℃ 二叉树的遍历

二叉树，每个节点最多有两个子树的树形结构，两个子树被称为左子树 | 右子树

从逻辑上来看，二叉树是递归定义的，直观的来看有5中基本类型：

5 types

a - 空树，没有任何节点
b - 只有一个父节点
c - 只有左子树
d - 只有右子树
e - 既有左子树也有右子树

从二叉树的递归特性入手，我们可以很轻松的写出二叉树的遍历，通常有3中遍历（这里就不展开详细概念了，只简单介绍）：前序遍历，中序遍历，后序遍历，

前序遍历 - 先访问根节点，再访问左子树，再访问右子树
中序遍历 - 先访问左子树，再访问根节点，再访问右子树
前序遍历 - 先访问左子树，再访问右子树，再访问根节点

很显然，贴合树的递归定义构造了3中遍历方式。

示例图

Python代码示例 | C++代码示例

2℃ n叉树的访问操作

从二叉树扩展到n叉树：

变的是：树的子树不再只有只有两棵子树，可以是n颗子树
不变的是：树的定义仍旧遵循递归特性

当我要将最新生成的子配置添加到已经生成到的配置结果树中，我需要做的是：

访问这颗n叉树，找到我需要插入子配置的位置（需要子配置的父节点），然后插入到该父节点中形成新的配置结果树

对于n叉树的遍历我们同样可以采用那3中遍历方式，也有另外的方式称之为深度优先DFS（Depth First Search），广度优先BFS（Breadth First Search）

DFS - 从树顶开始找，找到第一棵不为空的子树，从这棵树开始，接着访问它的第一颗不为空的子树，总是刨根问底，深度优先
BFS - 从树顶开始，访问不为空的子树，访问完后，在访问下一层的子树，展开查找，广度优先

从递归的角度来看目录树，会发现树结构的本质都是相同的，不要被它层层叠叠的结构吓到，一个循环KO

伪代码如下

InsertConfigIntoConfigResult(root, id) {
  if (root) {
    if (root.id === id) {
       INSERTDATA() // 将数据插入      
    } else {
      root.children.forEach(element => {
        InsertConfigIntoConfigResult(element, id) // 访问子树
      })
    }
  }
}