以html节点为列进行深度优先和广度优先遍历
<div class="parent">
<div class="child-1">
<div class="child-1-1">
<div class="child-1-1-1">
1-1-1
</div>
</div>
<div class="child-1-2">
<div class="child-1-2-1">
1-2-1
</div>
<div class="child-1-2-2">
1-2-2
</div>
</div>
<div class="child-1-3">
1-3
</div>
</div>
<div class="child-2">
<div class="child-2-1">
2-1
</div>
<div class="child-2-2">
<div class="child-2-2-1">
2-2-1
</div>
</div>
</div>
<div class="child-3">
<div class="child-3-1">
3-1
</div>
</div>
</div>
1. 深度优先遍历
- 递归
// 方法1，传参保存结果
function deepTraversal1(node, nodeList = []) {
if (node) {
nodeList.push(node)
let children = node.children
for (let i = 0; i < children.length; i++) {
deepTraversal1(children[i], nodeList)
}
}
return nodeList
}
let result = deepTraversal1(document.querySelector(".parent"))
console.log(result)
// 方法2，concat拼凑结果
function deepTraversal2(node) {
let nodeList = []
if (node) {
nodeList.push(node)
let children = node.children
for (let i = 0; i < children.length; i++) {
nodeList = nodeList.concat(deepTraversal2(children[i]))
}
}
return nodeList
}
let result = deepTraversal2(document.querySelector(".parent"))
console.log(result)
- 非递归，栈表示法
function deepTraversal3(node) {
let stack = [], nodeList = []
if (node) {
stack.push(node)
let children = node.children
while(stack.length) {
let item = stack.pop()
nodeList.push(item)
let children = item.children
for (let i = children.length - 1; i >= 0; i--) {
stack.push(children[i])
}
}
}
return nodeList
}
let result = deepTraversal3(document.querySelector(".parent"))
console.log(result)
深度优先遍历
2. 广度优先遍历
- 队列表示法
function widthTraversal(node) {
let queue = [], nodeList = []
if (node) {
queue.push(node)
while(queue.length) {
let item = queue.shift()
let children = item.children
nodeList.push(item)
for (let i = 0; i < children.length; i++) {
queue.push(children[i])
}
}
}
return nodeList
}
广度优先遍历
