JS遞歸與二叉樹的遍歷

church 發布于2019-08-21 10:48 / 3460人閱讀

摘要：貌似大部分語言中的遞歸都差不多，之所以在標題加是因為搜了下后感覺網上用來描述這概念的不多，簡單地說遞歸就是函數調用自己的過程。

貌似大部分語言中的遞歸都差不多，之所以在標題加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，存在左子節點，執行向左遞歸，以此類推，就完成了這棵二叉樹的中序遍歷

附張遍歷順序示意圖：

GPU云服務器云服務器二叉樹的遍歷非遞歸二叉樹遍歷 JS二叉樹遍歷二叉樹的存儲

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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