Js二叉树与多叉树的遍历
二叉树的顺序存储结构就是用一维数组存储二叉树中的各个结点，并且结点的存储位置能体现结点之间的逻辑关系。
二叉树的遍历
二叉树的遍历有三种方式，如下：
（1）先序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。
（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。
（3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。
假设dom结构如下：
<div id="tree">
<div>
<div>
<div></div>
<div></div>
</div>
<div>
<div></div>
<div></div>
</div>
</div>
<div>
<div>
<div></div>
<div></div>
</div>
<div>
<div></div>
<div></div>
</div>
</div>
</div>遍历方式：
var arr = [];
// 递归先序遍历
function recurDLR(node) {
if (!node) {
return;
}
arr.push(node);
recurDLR(node.firstElementChild);
recurDLR(node.lastElementChild);
}
// 递归中序遍历
function recurLDR(node) {
if (!node) {
return;
}
recurLDR(node.firstElementChild);
arr.push(node);
recurLDR(node.lastElementChild);
}
// 递归后序遍历
function recurLRD(node) {
if (!node) {
return;
}
recurLRD(node.firstElementChild);
recurLRD(node.lastElementChild);
arr.push(node);
}多叉树结构遍历
// 递归先序遍历 先遍历子节点 再遍历根节点
function recurDLR(node) {
if (!node) {
return;
}
arr.push(node);
for (let i = 0; i < node.children.length; i++) {
if (node.children[i].nodeName.toLowerCase() === 'div') {
recurDLR(node.children[i]);
}
}
}
// 递归后序遍历 先遍历根节点 再遍历子节点
function recurLRD(node) {
if (!node) {
return;
}
for (let i = 0; i < node.children.length; i++) {
if (node.children[i].nodeName.toLowerCase() === 'div') {
recurLRD(node.children[i]);
}
}
arr.push(node);
}
// 层序遍历 从根节点一层一层向下遍历
// 原理就是利用数组的后进先出 存储dom节点
function recurLDR(node) {
var stack = [];
stack.push(node);
var del = stack.shift();
while (del) {
for (let i = 0; i < del.children.length; i++) {
if (del.children[i].nodeName.toLowerCase() === 'div') {
stack.push(del.children[i]);
}
}
arr.push(del);
del = stack.shift();
}
}本文内容仅供个人学习、研究或参考使用，不构成任何形式的决策建议、专业指导或法律依据。未经授权，禁止任何单位或个人以商业售卖、虚假宣传、侵权传播等非学习研究目的使用本文内容。如需分享或转载，请保留原文来源信息，不得篡改、删减内容或侵犯相关权益。感谢您的理解与支持！
