一年网站维护北京关键词优化服务
近段时间去面试的时候，被面试官问到如何遍历查询一个颗树的时候，可能最近自己看了数据结构的书之后，隐隐约约就想到二叉树的三种排序（前序、中序、后序），但是当时自己没有想起这三种排序的名字，只是回答说好像有三种，但是当时面试官好像突然明白了，说你是不是想说前序、中序、后序，我回答说是的，然后面试官淡淡回了一句说不是，后面我回去查了下，才知道不是，突然间顿悟了，不就是我们经常所说的递归吗？感觉自己回答到点子上面
但是只回递归的话，无法加分的，从网上查了之后，才知道除了递归，还有循环，再拓展一点，大体分为深度优先遍历和广度优先遍历两种方法，下面我们逐一讲解。
我们正常的思维或许第一采取的就是深度优先遍历，然后用递归实现，如下：
先定义一颗树：
let tree = [
{id: '1',name: '节点1',children: [{id: '1-1',name: '节点1-1'}]
},
{id: '2',name: '节点2',children: [{id: '2-1',name: '节点2-1'},{id: '2-2',name: '节点2-2',children: [{id: '2-2-1',name: '节点2-2-1'}]}]
},
{id: '3',name: '节点3'
}
]
然后用递归实现：
function treeIterator(tree, func) {tree.forEach((node) => {func(node)node.children && treeIterator(node.children, func)})
}
用循环实现的方法：
function treeIterator(tree, func) {let node, curTree = [...tree]while ((node = curTree.shift())) {func(node)node.children && curTree.unshift(...node.children)}
}
打印出来：
节点1 节点1-1 节点2 节点2-1 节点2-2 节点2-2-1 节点3...
如果再问你用了什么数据结构，怎么回答呢？
答案：用了栈，先进后出！
广度优先遍历
循环实现：
function treeIterator(tree, func) {let node, curTree = [...tree]while ((node = curTree.shift())) {func(node)node.children && curTree.push(...node.children)}
}
打印出来：
节点1 节点2 节点3 节点1- 1节点2-1 节点2-2 节点2-2-1...
继续问用了什么数据结构？
答案：用了队列，先进先出！！
参考博客：https://blog.csdn.net/w544924116/article/details/119712713?spm=1001.2014.3001.5506