V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
waiaan
V2EX  ›  JavaScript

临时写了一个遍历树的方法,求改成尾递归。

  •  
  •   waiaan · 2020-05-15 11:36:13 +08:00 · 1415 次点击
    这是一个创建于 1414 天前的主题,其中的信息可能已经有所发展或是发生改变。
      var traverseNode = function (node, i, arr, cb) {
        cb(node, i, arr);
        if (node.children) {
          var children = node.children;
          for (var i = 0; i < children.length; i++) {
            var childNode = children[i];
            traverseNode(childNode, i, children, cb)  // 如何改成尾递归的形式
          }
        }
      }
    
      var traverseTree = function (tree, cb) {
        for (var i = 0; i < tree.length; i++) {
          traverseNode(tree[i], i, tree, cb)
        }
      }
    

    谢谢。

    3 条回复    2020-05-18 09:04:34 +08:00
    autoxbc
        1
    autoxbc  
       2020-05-15 21:04:23 +08:00
    尾递归有这么几个要点:

    1. 计算出中间结果,传递给下一次运算
    2. 怎样得到下一次计算需要的数据
    3. 递归终点

    对于在结构数据上递归,第二条稍微复杂一些。数据不是一维的,那么需要设计一个无遗漏,最好也不重复的迭代规则

    不确定你的函数怎么改写成尾递归,我只是写了一个简单的深度优先的节点遍历

    function traverseNode( node , cb , top , back )
    {
    var top = top || node ;

    if( back || node.children.length === 0 )
    {
    cb(node);
    if( node === top )
    return;

    if(node.nextElementSibling)
    return traverseNode( node.nextElementSibling , cb, top );

    if(node.parentNode)
    return traverseNode( node.parentNode , cb , top , true );
    } else {
    return traverseNode( node.children[0] , cb , top );
    }
    }

    以及,对于节点这种特殊数据,有更好的方法可以一次获得所有子节点(包括自身)

    [ node , node.querySelectorAll('*') ]
    autoxbc
        2
    autoxbc  
       2020-05-15 21:13:45 +08:00
    top 参数的意思是,当递归回自身时,表示已经处理所有节点,所以直接退出

    back 参数的意思是,从子节点返回父节点时,告诉函数子节点已处理完毕
    waiaan
        3
    waiaan  
    OP
       2020-05-18 09:04:34 +08:00
    @autoxbc 谢谢,我学习一下。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5312 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 08:28 · PVG 16:28 · LAX 01:28 · JFK 04:28
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.