집 >웹 프론트엔드 >JS 튜토리얼 >다중 트리에 대한 재귀 순회 및 비재귀 순회 알고리즘의 JavaScript 공유

다중 트리에 대한 재귀 순회 및 비재귀 순회 알고리즘의 JavaScript 공유

小云云원래의: 2018-05-16 16:42:362699검색

이 글에서는 JavaScript로 구현된 다중 트리의 재귀적 순회와 비재귀적 순회 알고리즘을 주로 소개합니다. JavaScript 다중 트리에서 json 노드의 재귀적 순회와 비재귀적 순회를 예제 형식으로 자세히 분석합니다. 도움이 필요한 경우 다음을 참조하세요. 모든 사람에게 도움이 되기를 바랍니다.

발표 전 준비

데모 프로젝트 파일 구조:

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

각 파일 설명:

색인 .html 프레젠테이션에 사용되는 HTML 파일입니다.
jsonData.js는 다중 트리의 JSON 데이터를 저장합니다.
recurrenceTree.js 재귀 알고리즘은 트리를 순회합니다.
noRecurrenceTree.js 트리 순회를 위한 비재귀 알고리즘입니다.

jsonData.js

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

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.jb51.net 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 pObj = document.getElementById("app");
  pObj.innerHTML = pObj.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);

비순회

noRe currenceTree .js

// 遍历单个节点
function traverseNode2(node){
  var pObj2 = document.getElementById("app2");
  pObj2.innerHTML = pObj2.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 공유

관련 기사