深度优先遍历和广度优先遍历
程序员文章站
2022-05-21 15:06:28
...
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>deepTraversal</title>
</head>
<body>
<div class="parent">
<div class="child-1">
<div class="child-1-1">
<div class="child-1-1-1">
a
</div>
</div>
<div class="child-1-2">
<div class="child-1-2-1">
b
</div>
</div>
<div class="child-1-3">
c
</div>
</div>
<div class="child-2">
<div class="child-2-1">
<div class="child-2-1-1">
d
</div>
</div>
<div class="child-2-2">
<div class="child-2-2-1">
e
</div>
</div>
<div class="child-2-3">
f
</div>
</div>
</div>
<script>
//深度优先遍历
//第一种递归方法
function deepTraversal (node, nodeList = []) {
if (node) {
nodeList.push(node);
let children = node.children;
for (let i = 0; i < children.length; i++) {
deepTraversal(children[i], nodeList);
}
}
return nodeList;
}
//第二种递归方法
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;
}
//非递归方法（采用栈）
function deepTraversal3 (node) {
let nodeList = [];
let stack = [];
if (!node) return nodeList;
stack.push(node);
while(stack.length) {
let item = stack.pop();
nodeList.push(item);
let children = node.children;
for (let i = children.length - 1; i > 0; i--) {
stack.push(children[i]);
}
}
return nodeList;
}
//广度优先遍历(采用队列)
function widthTraversal (node) {
let nodeList = [];
if (!node) return nodeList;
let stack = [];
stack.push(node);
while (stack.length) {
let item = stack.shift();
nodeList.push(item);
let children = item.children;
for (let i = 0; i < children.length; i++) {
stack.push(children[i]);
}
}
return nodeList;
}
let node = document.getElementsByClassName('parent')[0];
console.log('widthTraversal:', widthTraversal(node));
</script>
</body>
</html>
上一篇： 二维矩阵查找（矩阵/二维矩阵/杨氏矩阵/查找/搜索）
下一篇： 广度优先搜索与深度优先搜索