JavaScript實現多叉樹的遞歸遍歷和非遞歸遍歷算法操作示例

2024-05-06 16:42:23

字體：大中小

來源：轉載

供稿：網友

本文實例講述了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.survivalescaperooms.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);

本機測試效果：

JavaScript,多叉樹,遞歸遍歷,非遞歸遍歷,算法