JS递归与二叉树的遍历

church 发布于2019-08-21 10:48 / 3332人阅读

摘要：貌似大部分语言中的递归都差不多，之所以在标题加是因为搜了下后感觉网上用来描述这概念的不多，简单地说递归就是函数调用自己的过程。

貌似大部分语言中的递归都差不多，之所以在标题加JS是因为搜了下后感觉网上用js来描述这概念的不多，简单地说递归就是函数调用自己的过程。下面的栗子可以很直观地展示递归的执行过程：

function rec(x){
if(x!==1){
   console.log(x)
    rec(x-1)
   console.log(x) 
   }   
}
rec(5) //输出为5 4 3 2 2 3 4 5

由这个栗子?可知：在递归调用语句前的语句执行是正常顺序，但是递归调用语句后的执行却是相反的也就是说在递归还没有完成时，函数的输出结果暂时被挂起，因为一般在计算机中，是以栈的形式来实现递归，这个过程如下：

5 rec(4)     //第一级
5 4 rec(3)   //第二级
5 4 3 rec(2)  //第三级
5 4 3 2 rec(1)  //第四级
console.log() 2 3 4 5  //以出栈形式输出结果

当递归完成时，执行流开始处理上一级递归中的递归语句后面的语句，在这里是输出当前变量console.log(x)

递归非常适用于相同函数不同参数的迭代循环。但是因为需要为每一级的递归开辟内存所以递归的开销相对来说蛮大的，在很多编程的语言中,对于递归的开销问题有个TCO优化（Tail Call Optimization）戳这篇博客了解更多?[翻译] JS的递归与TCO尾调用优化

之所以想起码这篇博客，是因为最近看《算法与数据结构JavaScript描述》（请拉黑此书，bug极多，极不推荐）中使用递归遍历二叉树的算法挺绕的，写篇博客厘清下。
这里直接借用原书的代码(有删改)，以二叉树的的中序遍历为例：

// 节点对象的构造函数
function Node(data, left, right) {
   this.data = data;
   this.left = left;
   this.right = right;
   this.show = show;
}

function show() {
   return this.data;
}
//二叉树的构造函数
function BST() {
   this.root = null;
   this.insert = insert;
   this.inOrder = inOrder;
   
}
//插入方法
function insert(data) {
   var n = new Node(data, null, null);
   if (this.root == null) {
      this.root = n;
   }
   else {
      var current = this.root;
      var parent;
      while (true) {
         parent = current;
         if (data < current.data) {
            current = current.left;
            if (current == null) {
               parent.left = n;
               break;
            }
         }
         else {
            current = current.right;
            if (current == null) {
               parent.right = n;
               break;
            }
         }
      }
   }
}
//调用两次递归遍历二叉树
function inOrder(node) {
   if (!(node == null)) {
      inOrder(node.left);
      console.log(node.show() )
      inOrder(node.right);
   }
}

//将以下数据导入二叉树
nums.insert(23)
nums.insert(45)
nums.insert(16)
nums.insert(37)
nums.insert(3)
nums.insert(99)
nums.insert(22)

  
//中序遍历二叉树
inOrder(nums.root)  
 /*
输出结果为：
 3
 16
 22
 23
 37
 45
 99
*/

在inOrder函数中使用了两次递归，它的执行顺序是：沿左边找到最小值3，第一次递归完成，之前被挂起的语句开始以出栈的形式执行，输出无子节点的节点3，然后回到上一级递归，输出其上一级递归中的节点16，在节点16处，存在子节点，于是执行向右递归，执行到无子节点的22，输出22后返回到节点16 ，执行流继续往回执行，执行到根节点23，输出23后又插入一次向右递归，右递归到45，存在左子节点，执行向左递归，以此类推，就完成了这棵二叉树的中序遍历

附张遍历顺序示意图：

海外云主机私有云二叉树的遍历非递归二叉树遍历 JS二叉树遍历二叉树的存储

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/86226.html

学习JavaScript数据结构与算法（四）：二叉搜索树

摘要：像刚才的这幅图，就是二叉搜索树。而我们本文要学习的内容，就是如何写一个二叉搜索树。但在二叉搜索树中，我们把节点成为键，这是术语。前端路漫漫，且行且歌的前端乐园原文链接寒假前端学习学习数据结构与算法四二叉搜索树本系列的第一篇文章: 学习JavaScript数据结构与算法（一），栈与队列第二篇文章：学习JavaScript数据结构与算法（二）：链表第三篇文章：学习JavaScript数据...

ingood 2019-08-19 17:26 评论0 收藏0
数据结构之二叉树（java版）

摘要：二叉树是数据结构中很重要的结构类型，学习数据结构也是深入学习编程的必由之路，这里我们简单介绍下我对于二叉树的理解，水平有限，如有错误还请不吝赐教。二叉树是数据结构中很重要的结构类型，学习数据结构也是深入学习编程的必由之路，这里我们简单介绍下我对于二叉树的理解，水平有限，如有错误还请不吝赐教。首先照例定义一个二叉树的节点类 class Node { private int ...

JayChen 2019-08-14 18:02 评论0 收藏0
JavaScript二叉树及各种遍历算法详情

　　在之前的文章中我们有讲过树的相关知识，例如，树的概念、深度优先遍历和广度优先遍历。这篇文章讲述了一个特殊的树——二叉树。什么是二叉树　　二叉树是每个节点最多只能有两个子节点的树，如下图所示：　　一个二叉树具有以下几个特质：　　要计算在每层有多少个点，可以依据公式2^(i-1)个(i是树的第几层)；　　如果这颗二叉树的深度为k，那二叉树最多有2^k-1个节点；　　在一个非空的二叉树中，若使...

3403771864 2022-09-18 22:18 评论0 收藏0