JavaScript实现多叉树的递归遍历和非递归遍历算法操作示例

2019-11-19 14:23:11

字体：大中小

来源：转载

供稿：网友

本文实例讲述了JavaScript实现多叉树的递归遍历和非递归遍历算法操作。分享给大家供大家参考，具体如下：

演示之前的准备工作

演示项目的文件结构：

index.html
jsonData.js
recurrenceTree.js
noRecurrenceTree.js

解释一下各个文件：

index.html 是用来演示的 HTML 文件。
jsonData.js 里面存储着多叉树的JSON数据。
recurrenceTree.js 递归算法遍历树。
noRecurrenceTree.js 非递归算法遍历树。

jsonData.js

/** * 用于演示的 JSON 树形数据结构 */var root = {  name:'D盘',  children:[    {      name:'学习',      children:[        {          name:'电子书',          children:[            {              name:'文学',              children:[                {                  name:'茶馆'                },                {                 name:'红与黑'                }              ]            }          ]        }      ]    },    {      name:'电影',      children:[        {          name:'美国电影'        },        {          name:'日本电影'        }      ]    }  ]}

index.html

<!DOCTYPE html><html lang="en"> <head>  <meta charset="UTF-8">  <meta name="renderer" content="webkit"/>  <meta http-equiv="x-ua-compatible" content="ie=edge, chrome=1">  <meta http-equiv="Cache-Control" content="max-age: 31536000">  <title>www.VeVB.COm js多叉树遍历</title>  <meta name="viewport" content="width=device-width, initial-scale=1.0, minimum-scale=1.0, maximum-scale=1.0, user-scalable=no">  <meta name="wap-font-scale" content="no">  <meta name="author" content="">  <meta name="keywords" content="">  <meta name="description" content="">  <script type="text/javascript" src="jsonData.js"></script> </head> <body>  递归遍历：<span id="app"></span>  <script type="text/javascript" src="recurrenceTree.js"></script>  <hr>  非递归遍历：<span id="app2"></span>  <script type="text/javascript" src="noRecurrenceTree.js"></script> </body></html>

递归遍历

recurrenceTree.js

// 遍历单个节点function traverseNode(node){  var divObj = document.getElementById("app");  divObj.innerHTML = divObj.innerHTML + " " + node.name;}// 递归遍历树// 作者：张超function traverseTree(node){  if (!node) {    return;  }  traverseNode(node);  if (node.children && node.children.length > 0) {    var i = 0;    for (i = 0; i < node.children.length; i++) {      this.traverseTree(node.children[i]);    }  }}traverseTree(root);

非递归遍历

noRecurrenceTree.js

// 遍历单个节点function traverseNode2(node){  var divObj2 = document.getElementById("app2");  divObj2.innerHTML = divObj2.innerHTML + " " + node.name;}// 非递归遍历树// 作者：张超function traverseTree2(node){  if (!node) {    return;  }  var stack = [];  stack.push(node);  var tmpNode;  while (stack.length > 0) {    tmpNode = stack.pop();    traverseNode2(tmpNode);    if (tmpNode.children && tmpNode.children.length > 0) {      var i = tmpNode.children.length - 1;      for (i = tmpNode.children.length - 1; i >= 0; i--) {        stack.push(tmpNode.children[i]);      }    }  }}traverseTree2(root);

本机测试效果：