javascript - 算法：递归 与 循环的转换

问题描述

问 题

参考递归算法文献：链接描述
递归过程以及递归过程的优化文献：链接描述

递归到非递归算法转化的概念截图：

这边有一个二叉查找树类，内部包含了两个中序遍历方法：一个是递归实现的（已实现）；一个循环实现的（未实现，求实现 + 结合上面概念图进行描述：如何用堆栈的方式实现递归到非递归的转化）：

// 二叉查找树（类比链表）
function Tree(data){
    this.root  = null;
    this.index = 0;
}

Tree.prototype = {
    append: function(data){
        var n = new Node(data , this) ,
            c = null ,
            p = null;

        if (this.root === null) {
            this.root   = n;
        } else {
            c = this.root;

            while (true)
                {
                    p = c;

                    if (n.data < c.data) {
                        c = c.left;
                        
                        if (c === null) {
                            p.left = n;
                            break;
                        }
                    } else {
                        c = c.right;

                        if (c === null) {
                            p.right = n;
                            break;
                        }
                    }
                }
        }
    } , 

    /* 
     * 中序遍历 BST（二叉查找树）：递归方式
     * @param Mixed   node       开始节点
     * @param String  sortType   排序类型
     * @return Array
     */
    midTraversalRec: function(node , sortType){
        var rel = [] ,
            sortTypeRange = ['asc' , 'desc'] ,
            sort ,
            node = node === undefined ? this.root : node;
        
        // 范围检测
        if (!contain(sortType , sortTypeRange)) {
            error('参数 2 超出支持的范围');
        }

        // 核心排序函数 + 结构重组
        sort = function(n){
            if (n !== null) {
                if (sortType === 'asc') {
                    sort(n.left);
                    rel.push(n.data);
                    sort(n.right);
                } else {
                    sort(n.right);
                    rel.push(n.data);
                    sort(n.left);
                }
            }
        };
        
        sort(node);

        return rel;
    } ,
    
    // 中序遍历：循环方式（怎么实现？？）
    midTraversalLoop: function(node , sortType){}
};


// 节点
function Node(data , tree){
    this.data = data;
    this.left = null;
    this.right = null;
    
    // 存储序列
    this.index = tree.index;
    tree.index += 1;
}

我不太懂的是这个过程：

麻烦帮我实现下：二叉树循环方式实现中序遍历，并结合这个描述，在代码中做必要的标注...，谢谢

解决方案

加班回来时间不多，就先针对堆栈循环举个栗子吧

---

<script>
function example(foo) {
  var arr = [];
  var result;
  var begin = false;
  return function sum (n) {
    arr.push(n);
    if(!begin) {
      begin = true;
      while (arr.length){
        result = foo(arr.shift());
      }
      return result;
    }
  };
}
var count = example(function (n) {
  return n < 10E5 ? count(n * 2) : n;
});
count(1);
</script>

阮一峰大神的ES6介绍网站上有提到递归优化 链接描述

这篇关于javascript - 算法：递归 与 循环的转换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！