国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

使用javascript實現(xiàn)排序二叉樹（2）

susheng / 2422人閱讀

摘要：使用實現(xiàn)排序二叉樹上一篇文章我們構(gòu)造了基本的一個排序二叉樹的數(shù)據(jù)結(jié)構(gòu)，但是僅僅是定義了一個方法去創(chuàng)建二叉排序樹，今天我們來給我們的數(shù)據(jù)結(jié)構(gòu)添加一些遍歷的功能。

使用javascript實現(xiàn)排序二叉樹（2）

上一篇文章我們構(gòu)造了基本的一個排序二叉樹的數(shù)據(jù)結(jié)構(gòu)，但是僅僅是定義了一個insert方法去創(chuàng)建二叉排序樹，今天我們來給我們的數(shù)據(jù)結(jié)構(gòu)添加一些遍歷的功能。

二叉樹的三種遍歷方式（以根節(jié)點為準來定義前、中、后）的介紹及其應(yīng)用場景：

前序遍歷

順序：根節(jié)點 => 左子樹 => 右子樹

應(yīng)用：可以用來構(gòu)建文件的目錄結(jié)構(gòu)，輸出所有目錄并分層

中序遍歷

順序：左子樹 => 根節(jié)點 => 右子樹

應(yīng)用：可以進行排序，輸出的結(jié)果是一個遞增的序列

后續(xù)遍歷

順序：左子樹 => 右子樹 => 根節(jié)點

應(yīng)用：后續(xù)遍歷是先遍歷子樹，最后到根節(jié)點，可以實現(xiàn)統(tǒng)計節(jié)點數(shù)、計算文件夾大小的功能

思考 ：

遍歷的方法是給誰用的，是否需要暴露出去

如果暴露出去，怎樣設(shè)計才能讓調(diào)用者能夠獲取到每一個節(jié)點并且進行對應(yīng)的操作

結(jié)論 ：

肯定是要暴露出去給別人調(diào)用的

給別人調(diào)用，具體的邏輯是不確定的，所以應(yīng)該是調(diào)用者傳入一個函數(shù)，我們在遍歷的時候把每一次的節(jié)點都傳給這個函數(shù)，并且去調(diào)用這個函數(shù)，這樣我們不用管具體函數(shù)的邏輯，反正已經(jīng)把它想要的 節(jié)點 給他了，具體怎樣操作我們不用管。

分析完畢之后，依然是上次的代碼，我們給他添加前序中序和后續(xù)遍歷的方法：

function BinaryTree(){
  var root = null; //根節(jié)點默認為null
  //節(jié)點類型的構(gòu)造函數(shù)
  function Node(key){
    this.key = key;
    this.left = null;
    this.right = null;
  }
  //插入方法
  this.insert = function(key){     
    var newNode = new Node(key);
    if(root === null){
       root = newNode;
    }else{
       insertNode(root,newNode)
    }
  }
  var insertNode = function(node,newNode){
    if(newNode.key < node.key){
      if(node.left === null){
         node.left = newNode;
      }else{
         insertNode(node.left,newNode)
      }
    }else{
      if(newNode.key > node.key){
        if(node.right === null){
          node.right = newNode;
        }else{
          insertNode(node.right,newNode)
        }
      }
    }
  }
  
  /*--------------------------------------------------------*/
  /*
      前序遍歷： 根節(jié)點 => 左子樹 => 右子樹
  */
  this.preTravel = function(callback){
    //和上面插入操作類似，都用一個內(nèi)部的函數(shù)來實現(xiàn)具體的邏輯，因為需要使用root
     preTravelNode(root,callback); 
  }   
  /* 
      邏輯：
          1. 判斷傳入的節(jié)點是否為null，如果為null就直接return
          2. 如果不為null，則繼續(xù)對該節(jié)點下的left和right進行遞歸調(diào)用
          3. 具體的調(diào)用順序根據(jù)為 根節(jié)點 => 左子樹 => 右子樹
  */
  function preTravelNode(node,callback){
    if(node !== null){ 
       callback(node.key); 
       preTravelNode(node.left,callback);
       preTravelNode(node.right,callback);
    }
  }
  
  //中序遍歷
  this.middleTravel = function(callback){
    middleTravelNode(root,callback);
  }
  function middleTravelNode(node,callback){
    if(node !== null){
       middleTravelNode(node.left,callback);
       callback(node.key);
       middleTravelNode(node.right,callback);
    }
  }
  
  //后續(xù)遍歷
  this.nextTravel = function(callback){
    nextTravelNode(root,callback);
  }
  function nextTravelNode(node,callback){
    if(node !== null){
       nextTravelNode(node.left,callback);
       nextTravelNode(node.right,callback);
       callback(node.key);
    }
  }
}

var nodes = [8,7,3,4,6,5,2,9,12]
var binaryTree = new BinaryTree();
nodes.forEach((item)=>{
    binaryTree.insert(item)
})
//測試前序遍歷
binaryTree.beforeTravel((key)=>{
  console.log(key) // 8,7,3,2,4,6,5,9,10
})
console.log("--------------------")
//中序遍歷
binaryTree.middleTravel((key)=>{
  console.log(key) // 2,3,4,5,6,7,8,9,10
})
console.log("--------------------")
//后續(xù)遍歷
binaryTree.nextTravel((key)=>{
  console.log(key) // 2,5,6,4,3,7,10,9,8
})

具體的邏輯 ：

判斷傳入的節(jié)點是否為null，如果為null就直接return

如果不為null，則繼續(xù)對該節(jié)點下的left和right進行遞歸調(diào)用

具體的調(diào)用順序根據(jù)前序、中序、后序、的訪問節(jié)點順序去修改調(diào)用的順序

還是放上這個二叉樹的圖，根據(jù)圖去對比測試的遍歷結(jié)果更直觀：

重點 ：

怎樣設(shè)計遍歷方法，調(diào)用者傳什么東西進來，我們要暴露什么東西出去，這個地方得想明白

下期內(nèi)容 ：

實現(xiàn)二叉樹的節(jié)點查找功能

實現(xiàn)二叉樹中節(jié)點的刪除功能

實現(xiàn)一個二叉樹的一個小游戲

上期內(nèi)容 ：

使用javascript定義一個排序二叉樹

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/97120.html

相關(guān)文章

  • 使用javascript實現(xiàn)排序二叉樹（1）

    摘要：使用實現(xiàn)排序二叉樹排序二叉樹的定義二叉樹的基礎(chǔ)上，左節(jié)點比父節(jié)點要小，右節(jié)點比父節(jié)點要大的二叉樹，叫排序二叉樹。下期內(nèi)容實現(xiàn)排序二叉樹的中序前序后續(xù)遍歷實現(xiàn)二叉樹的節(jié)點查找功能實現(xiàn)排序二叉樹的刪除節(jié)點功能應(yīng)用排序二叉樹實現(xiàn)一個小游戲 使用javascript實現(xiàn)排序二叉樹（1） 排序二叉樹的定義： 二叉樹的基礎(chǔ)上，左節(jié)點比父節(jié)點要小，右節(jié)點比父節(jié)點要大的二叉樹，叫排序二叉樹。 show...

    Caicloud 評論0 收藏0

  • JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 非線性表中的樹、堆是干嘛用的 ？其數(shù)據(jù)結(jié)構(gòu)是怎樣的 ？

    摘要：筆者寫的數(shù)據(jù)結(jié)構(gòu)與算法之美系列用的語言是，旨在入門數(shù)據(jù)結(jié)構(gòu)與算法和方便以后復(fù)習(xí)。非線性表中的樹堆是干嘛用的其數(shù)據(jù)結(jié)構(gòu)是怎樣的希望大家?guī)е@兩個問題閱讀下文。其中，前中后序，表示的是節(jié)點與它的左右子樹節(jié)點遍歷訪問的先后順序。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 想學(xué)好前端，先練好內(nèi)功，內(nèi)功不行，...

    singerye 評論0 收藏0

  • 學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)(四)——樹

    摘要：原文博客地址學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)四樹知乎專欄簡書專題前端進擊者知乎前端進擊者簡書博主博客地址的個人博客人之所能，不能兼?zhèn)?，棄其所短，取其所長。通常子樹被稱作左子樹和右子樹。敬請期待數(shù)據(jù)結(jié)構(gòu)篇最后一篇文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)五圖參考文章樹數(shù)據(jù)結(jié)構(gòu)二叉樹 前言 總括： 本文講解了數(shù)據(jù)結(jié)構(gòu)中的[樹]的概念，盡可能通俗易懂的解釋樹這種數(shù)據(jù)結(jié)構(gòu)的概念，使用javascript實現(xiàn)了樹，如有紕漏，歡迎批評指正。 ...

    Dean 評論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法:二叉樹算法

    摘要：因此，根據(jù)題目給出的先序遍歷和中序遍歷，可以畫出二叉樹選參考數(shù)據(jù)結(jié)構(gòu)與算法描述實現(xiàn)二叉樹算法淺談數(shù)據(jù)結(jié)構(gòu)二叉樹慕課網(wǎng)實現(xiàn)二叉樹算法前端樹控件騰訊軟件開發(fā)面試題 內(nèi)容銜接上一章 數(shù)據(jù)結(jié)構(gòu)與算法:常見排序算法 內(nèi)容提要 什么是樹 　　- 為什么使用樹 二叉樹 二叉查找樹 紅黑樹 Ｂ、Ｂ＋樹 堆 伸展樹 樹 可以點擊鏈接感受下筆者用d3.js畫的tree https://codepen...

    Little_XM 評論0 收藏0

  • JavaScript實現(xiàn)簡單二叉查找樹

    摘要：二叉查找樹二叉查找樹也叫二叉搜索樹它只允許我們在左節(jié)點存儲比父節(jié)點更小的值，右節(jié)點存儲比父節(jié)點更大的值，上圖展示的就是一顆二叉查找樹。 前兩天接到了螞蟻金服的面試電話，面試官很直接，上來就拋出了三道算法題。。。 其中有一道關(guān)于二叉樹實現(xiàn)中序遍歷的，當(dāng)時沒回答好，所以特意學(xué)習(xí)了一把二叉樹的知識，行文記錄總結(jié)。 二叉樹&二叉查找樹 showImg(https://segmentfault....

    frank_fun 評論0 收藏0

發(fā)表評論

0條評論

susheng

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<