# 前端算法之与数据结构-广度遍历和深度遍历与二叉树遍历

-类似二叉树的先序遍历

```/* 广度遍历dom */
//非递归版本

//新建队列和nodes列表
//队列不为空，取出第一个元素，push进nodes，循环添加children进队列
//返回nodes
let nodes = []
let queue = []
if(node){
queue.push(node)
while(queue.length){
let item = queue.shift()
let children = item.children
nodes.push(item)
// 队列，先进先出
// nodes = [] queue= [parent]
// nodes = [parent] queue= [child1,child2,child3]
// nodes = [parent, child1] queue= [child2,child3,child1-1,child1-2]
for(let i = 0;i){
queue.push(children[i])
}
}
}
return nodes
}```

-类似二叉树的层次遍历

```/* 深度遍历dom */
//非递归版本
let deepTraversal = (node) => {
let stack = []
let nodes = []
if (node) {
// 推入当前处理的node
stack.push(node)
while (stack.length) {
let item = stack.pop()
let children = item.children
nodes.push(item)
// node = [] stack = [parent]
// node = [parent] stack = [child3,child2,child1]
// node = [parent, child1] stack = [child3,child2,child1-2,child1-1]
// node = [parent, child1-1] stack = [child3,child2,child1-2]
for (let i = children.length - 1; i >= 0; i--) {
stack.push(children[i])
}
}
}
return nodes
}
//递归版本
let deepTraversal1 = (node) => {
let nodes =[]
if(node!== null) {
nodes.push(node)
let children = node.children;
for(let i = 0;i){
nodes = nodes.concat(deepTraversal(children[i]))
}
}
return nodes;
}
let parent = document.querySelector('.parent');
let joe = deepTraversal(parent);
console.log(joe);```

·         bfs利用队列实现，循环中做的是push => shift => push => shift

·         dfs利用栈实现，循环中做的是push => pop => push => pop

```/* 查找对应name路径 广度遍历 队列实现 bfs */
function bfs(target, name) {
const queue = [...target]
do {
const current = queue.shift()
if (current.children) {
queue.push(...current.children.map(x => ({ ...x, path: (current.path || current.name) + '-' + x.name })))
}
if (current.name === name) {
return current//返回整个目标对象
}
} while(queue.length)
return undefined
} ```
```/* 查找对应name路径 深度遍历 栈实现  dfs */
function dfs(target,name){
const stack = [...target]
do{
const current = stack.pop()
if(current.children){
stack.push(...current.children.map(x => ({...x,path:(current.path || current.name) + '-' + x.name})))
}
if(current.name === name){
return current.path//返回整个目标对象的path属性
}

}while(stack.length)
return undefined
}```
```/*  公共的搜索方法，mode默认bfs */
function commonSearch(target, name, mode) {
const stackOrQueue = [...target]
do {
const current = stackOrQueue[mode === 'dfs' ? 'pop' : 'shift']()
if (current.children) {
stackOrQueue.push(...current.children.map(x => ({ ...x, path: (current.path || current.name) + '-' + x.name })))
}
if (current.name === name) {
return current
}
} while(stackOrQueue.length)
return undefined
}```

```/* 搜索地区测试用例 */
const data = [{
id: '1',
name: '广东省',
children: [
{
id: '12',
name: '广州市',
children: [
{
id:'121',
name: '天河区'
},
{
id:'122',
name: '荔湾区'
}
]
}
]
}]
console.log(dfs(data,'天河区'))```

·         结果1：返回对象

·         结果2：返回对象的path属性

·         二叉树的前序遍历（根节点N在左右子树前）NLR - ABDECF

·        二叉树的中序遍历（根节点N在左右子树中）LNR - DBEAFC

·        二叉树的后序遍历（根节点N在左右子树后）LRN - DEBFCA

```/* 递归写法 */
/* 前序 */
const preorderTraversal = function (root, array=[]) {
if(root) {
array.push(root.val);
preorderTraversal(root.left, array);
preorderTraversal(root.right, array);
}
return array;
}
/* 中序 */
const inorderTraversal = function(root, array= []) {
if(root) {
inorderTraversal(root.left, array);
array.push(root.val);
inorderTraversal(root.right, array);
}
return array;
}
/* 后序 */
const postorderTraversal = function(root, array = []) {
if(root){
postorderTraversal(root.left, array);
postorderTraversal(root.right, array);
array.push(root.val);
}
return array;
}

/* 非递归写法 */
/* 前序 */
const preorderTraversal1 = function (root) {
const result = [];
const stack = [];
let current = root;
while(current||stack.length > 0){
while(current){
//取根节点值，左节点入栈，循环到左节点为空
result.push(current.val);
stack.push(current);
current = current.left;
}
//节点出栈，再遍历右节点
current = stack.pop();
current = current.right;
}
return result;
}
/* 中序 */
const inorderTraversal1 = function (root) {
const result = [];
const stack = [];
let current = root;
while(current||stack.length > 0){
while(current){
//左节点入栈，循环到左节点为空
stack.push(current);
current = current.left;
}
//节点出栈，取节点值，再遍历右节点
current = stack.pop();
result.push(current.val);
current = current.right;
}
return result;
}
/* 后序 */
const postorderTraversal1 = function (root) {
const result = [];
const stack = [];
let last = null;
let current = root;
while(current || stack.length > 0) {
while(current) {
//左节点入栈，循环到左节点为空
stack.push(current);
current = current.left;
}
//取栈内最后一个节点，判断是为空或者已遍历过，则将节点值传入
current = stack[stack.length-1];
if(!current.right || current.right == last){
//节点出栈
current = stack.pop();
result.push(current.val);
last = current;
current = null;
//继续循环弹栈
} else {
//取右节点做遍历操作
current = current.right
}
}
return result;
}
/* 测试用例 */
const data = {
val:1,
left:{
val:2,
left:{
val:4,
},
right:{
val:5
}
},
right:{
val:3,
left:{
val:6
},
right:{
val:7
}
}
}
console.log('递归计算结果')
console.log(preorderTraversal(data))
console.log(inorderTraversal(data))
console.log(postorderTraversal(data))
console.log('非递归计算结果')
console.log(preorderTraversal1(data))
console.log(inorderTraversal1(data))
console.log(postorderTraversal1(data))

//递归计算结果
[ 1, 2, 4, 5, 3, 6, 7 ]
[ 4, 2, 5, 1, 6, 3, 7 ]
[ 4, 5, 2, 6, 7, 3, 1 ]
//非递归计算结果
[ 1, 2, 4, 5, 3, 6, 7 ]
[ 4, 2, 5, 1, 6, 3, 7 ]
[ 4, 5, 2, 6, 7, 3, 1 ]```