使用javascript實現排序二叉樹（1）

Caicloud 發布于2019-08-23 11:29 / 2724人閱讀

摘要：使用實現排序二叉樹排序二叉樹的定義二叉樹的基礎上，左節點比父節點要小，右節點比父節點要大的二叉樹，叫排序二叉樹。下期內容實現排序二叉樹的中序前序后續遍歷實現二叉樹的節點查找功能實現排序二叉樹的刪除節點功能應用排序二叉樹實現一個小游戲

使用javascript實現排序二叉樹（1）

排序二叉樹的定義：二叉樹的基礎上，左節點比父節點要小，右節點比父節點要大的二叉樹，叫排序二叉樹。

下面直接進入到我們的javascript代碼定義排序二叉樹的過程

/*
    分析二叉樹的結構得出，二叉樹由節點構成，每個節點又有自己的左右子樹。
    并且有一個根節點
*/
function BinaryTree(){
  var root = null; //根節點默認為null
  /*
    1.節點類型的構造函數,默認左右子樹都為空
  */
  function Node(key){
    this.key = key;
    this.left = null;
    this.right = null;
  }
  /*
      2.根據排序二叉樹的規律，我們定義一個插入節點的方法，去填充排序二叉樹。該方法是BinaryTree的一個方法，需要綁定在this上讓其他調用者能調用。而不是作為內部方法。
  */
  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)
        }
      }
    }
  }
}

/*
    測試：查看是否報錯，具體的流程邏輯可以通過打斷點來判斷是否與自己設想的一樣。
                      8
                   7     9
                 3         12
               2   4
                     6
                   5
*/
var nodes = [8,7,3,4,6,5,2,9,12]
var binaryTree = new BinaryTree();
nodes.forEach((item)=>{
    binaryTree.insert(item)
})

通過斷點調試，最后得到的一個二叉樹應該是這樣的。也是符合二叉排序樹的定義的。

重點

分析數據結構的一個規律，從而能夠定義出節點類型中有哪些屬性

方法不要都綁定在 this 上面，因為有些函數是不需要暴露出去的，而是內部使用的。

我覺得讓我收獲比較大的是這里的 insert 這個函數中又調用一個 insertNode 的函數，因為事實上真正的插入節點是需要兩個參數的，一個父節點，一個要插入的節點。所以會需要遞歸調用，如果不依靠 insertNode 直接用 insert方法去遞歸是沒法遞歸的。因為外部壓根獲取不到 root 。之前還想著只用一個方法就實現插入遞歸，但是確實不行。

下期內容

實現排序二叉樹的中序前序后續遍歷

實現二叉樹的節點查找功能

實現排序二叉樹的刪除節點功能

應用排序二叉樹實現一個小游戲

云服務器 GPU云服務器二叉樹排序樹規則實現二叉樹二叉樹 python二叉樹

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/97034.html

使用javascript實現排序二叉樹（2）

摘要：使用實現排序二叉樹上一篇文章我們構造了基本的一個排序二叉樹的數據結構，但是僅僅是定義了一個方法去創建二叉排序樹，今天我們來給我們的數據結構添加一些遍歷的功能。使用javascript實現排序二叉樹（2）上一篇文章我們構造了基本的一個排序二叉樹的數據結構，但是僅僅是定義了一個insert方法去創建二叉排序樹，今天我們來給我們的數據結構添加一些遍歷的功能。二叉樹的三種遍歷方式（以根節...

susheng 2019-08-23 11:33 評論0 收藏0
JavaScript 數據結構與算法之美 - 非線性表中的樹、堆是干嘛用的？其數據結構是怎樣的？

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

singerye 2019-08-26 10:09 評論0 收藏0
學習javascript數據結構(四)——樹

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

Dean 2019-08-20 13:47 評論0 收藏0
數據結構與算法:二叉樹算法

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

Little_XM 2019-08-22 11:09 評論0 收藏0
JavaScript實現簡單二叉查找樹

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

frank_fun 2019-08-23 10:38 評論0 收藏0