[嵌牛导读]
最近项目中使用了一种树型控件
这种树形控件被使用在这样的场景:
- 项目中单个配置需要多个子级配置完成后才可以生成
- 单个配置所涵盖的信息属于树形结构,类似于“n叉树”
这种树形控件,其展示方式采用级联层次的树形方式,简单易懂,层次分明,配置明确。我们的身边这种树形目录太多太多,像书本的目录,word文档的目录,一篇论文的目录,包括HTML页面层层叠叠的节点等等,所以我们有必要近距离看看这棵树。
[嵌牛鼻子]
BFS,DFS,二叉树,N叉树
[嵌牛提问]
- 二叉树是在接触数据结构,算法过程中一定会遇见的,如何从树顶到树底彻底的访问树的每一个节点?
- 将二叉树扩展到n叉树,有什么不同吗?
[嵌牛正文]
1℃ 二叉树的遍历
二叉树,每个节点最多有两个子树的树形结构,两个子树被称为左子树 | 右子树
从逻辑上来看,二叉树是递归定义的,直观的来看有5中基本类型:
- a - 空树,没有任何节点
- b - 只有一个父节点
- c - 只有左子树
- d - 只有右子树
- e - 既有左子树也有右子树
从二叉树的递归特性入手,我们可以很轻松的写出二叉树的遍历,通常有3中遍历(这里就不展开详细概念了,只简单介绍):前序遍历,中序遍历,后序遍历,
- 前序遍历 - 先访问根节点,再访问左子树,再访问右子树
- 中序遍历 - 先访问左子树,再访问根节点,再访问右子树
- 前序遍历 - 先访问左子树,再访问右子树,再访问根节点
很显然,贴合树的递归定义构造了3中遍历方式。
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) // 访问子树
})
}
}
}