快捷導(dǎo)航

JavaScript實現(xiàn)多叉樹的遞歸遍歷和非遞歸遍歷算法操作示例

更新時間：2018年02月08日 10:30:57 作者：zhangchao19890805

這篇文章主要介紹了JavaScript實現(xiàn)多叉樹的遞歸遍歷和非遞歸遍歷算法,結(jié)合實例形式詳細(xì)分析了JavaScript多叉樹針對json節(jié)點的遞歸與非遞歸遍歷相關(guān)操作技巧,需要的朋友可以參考下

本文實例講述了JavaScript實現(xiàn)多叉樹的遞歸遍歷和非遞歸遍歷算法操作。分享給大家供大家參考，具體如下：

演示之前的準(zhǔn)備工作

演示項目的文件結(jié)構(gòu)：

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

解釋一下各個文件：

index.html 是用來演示的 HTML 文件。
jsonData.js 里面存儲著多叉樹的JSON數(shù)據(jù)。
recurrenceTree.js 遞歸算法遍歷樹。
noRecurrenceTree.js 非遞歸算法遍歷樹。

jsonData.js

/**
 * 用于演示的 JSON 樹形數(shù)據(jù)結(jié)構(gòu)
 */
var root = {
  name:'D盤',
  children:[
    {
      name:'學(xué)習(xí)',
      children:[
        {
          name:'電子書',
          children:[
            {
              name:'文學(xué)',
              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.dbjr.com.cn 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

// 遍歷單個節(jié)點
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

// 遍歷單個節(jié)點
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);

本機(jī)測試效果：