树的遍历与图的遍历
研发时候，不要受原来的术语的影响，其实就是想着原来学过的或者看过的可以解决新遇到的问 题，这其实是侥幸心理，忘记原来的术语吧，那只是你创新的源泉。
遍历就是把节点按一定规则构成一个线性序列，不同的规则得到不同顺序的线性序列，仅此而已 。
算法是实际问题工作步骤的抽象，不要一味想算法，想想实际情况怎么做的，然后提取算法，然后优化。
不论怎样，要和具体的数据结构结合在一起。
一、树的遍历
对于树的遍历，有三种，就拿前序遍历来说，得到的序列不论怎么拆分(子串，就是要连续)，始
终要是根左右，跟在左右前面，左在右前面，有点DP类似最优子结构。
//中序 LDR if(null) { return ; } else { //分别输出左 根 右 } 无论前中后都是dfs，不过树的话，由于有了明确的children字段，不需要设置vis数组来确保只遍历一次，因为肯定知识便利了一次。
travel(node) { for(i=1:lengh) ｛ //.....处理node节点 if（null！=children） travel(children)； ｝ } 另一种写法是把for循环写在函数外面 树的层次遍历和BFS就很像了，总的来说就是DFS用栈，只不是栈是隐式栈，BFS用队列，用的是显式 列。
1.初始化一个队列，根入队 2.取对头，并访问 3.若左节点非空，入队；右节点非空入队 4.队不空，循环2 - 3，否则结束 二、图的遍历
2.1 BFS
自上而下，从左到右，也需要vis。是树层次的推广。
2.2 DFS
需要vis数组。是树的先跟的推广。
2.3 树和图区别与联系
图需要需要vis是怕循环遍历，这和树不一样，数不可能循环遍历。
相同点：从一点出发遍历相邻节点，对树来说是左右孩子。
不同点：图有多个相邻点，二叉树只有左右孩子，bfs需要vis记录访问过的节点。
比如a，左b右c，访问a，然后bc如队，然后访问b，a和b相邻，没有vis的话a又要被访问。
图有不连通情况，树的的dfs和bfs都不需要vis。
树是一种特殊的图。
三、线索树
每个节点增加2个字段分别指向节点的前驱和后继。前驱好搞，直接在travel增加一个参数 parentID，初始为null，在for内，if外直接指向该parentID，后继应该也不难，在if内，主要要看树的数据结构。
四、非递归遍历
BFS利用队列保存尚未遍历的节点或者子树，DFS用栈。
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
