<font id="zqva1"></font>
<rt id="zqva1"></rt>
  • <tt id="zqva1"></tt>
    <cite id="zqva1"></cite>

    <cite id="zqva1"><noscript id="zqva1"></noscript></cite>
      <rp id="zqva1"><meter id="zqva1"></meter></rp>

        <cite id="zqva1"></cite>
          <b id="zqva1"></b>
          <rp id="zqva1"></rp>
          <cite id="zqva1"></cite>

          <rt id="zqva1"></rt>

        1. <rp id="zqva1"></rp>

          JavaScript實現二叉排序樹

          時間:?2018-01-03閱讀:?1109標簽:?

          1. 初始化二叉樹

          function BinaryTree (arr) {
          	if (Object.prototype.toString.call(arr).slice(8, -1) !== 'Array') {
                  throw new TypeError('只接受一個數組作為參數')
              }
          	this.root = null; //根節點
              this.arr = arr || []; //接受傳入的參數-數組
            
              //初始化每個樹節點
              var TreeNode = function (key) {
                  this.key = key; //當前節點的值
                  this.left = null; //左子樹
                  this.right = null; //右子樹
              }
              
              //構建二叉樹
              this.init = function () {
                  if (!this.arr) {
                      console.warn('請選擇一個數組參數');
                  }
                  for (var i = 0, len = this.arr.length; i < len; i++) {
                      this.insert(this.arr[i])
                  }
              }
          
              //插入節點
              this.insert = function (key) {
                  var newNode = new TreeNode(key) //當前需要插入的節點
                  if (this.root === null) { //根節點不存在值時, 插入節點到根節點
                      this.root = newNode;
                  }else{
                      this.insertNode(this.root, newNode)
                  }
              }
              this.insertNode = function (rootNode, newNode) {
                  if (rootNode.key > newNode.key) { // 當前節點的key小于父節點時, 當前節點應該插入左子樹
                      if (rootNode.left === null) { //如果左子樹不存在節點時, 把當前節點放進去
                          rootNode.left = newNode;
                          return;
                      }
                      this.insertNode(rootNode.left, newNode) //左子樹存在節點, 再次遞歸與該左節點進行比較
          
                  }else{ // 當前節點的key大于或等于父節點時, 當前節點應該插入右子樹
                      if (rootNode.right === null) { //如果右子樹不存在節點時, 把當前節點放進去
                          rootNode.right = newNode;
                          return;
                      }
                      this.insertNode(rootNode.right, newNode) //右子樹存在節點, 再次遞歸與該右節點進行比較
                  }
              }
          }
          var arr = [8, 13,3,7,19,21,15];
          var tree = new BinaryTree(arr);
          tree.init();
          console.log(tree)
          結構如下圖:

          2. 二叉樹的遍歷

          /* 
            前序遍歷:根節點->左子樹->右子樹
            中序遍歷:左子樹->根節點->右子樹
            后序遍歷:左子樹->右子樹->根節點
          */
          


          前序遍歷

          //前序遍歷
              this.preorderTraversal = function (callback) {
                  if (this.root === null) {   //傳入根節點
                      console.warn('請先初始化二叉排序樹');
                      return;
                  }
                  var fn = function (node, callback) {
                      if (node !== null) {  //當前節點不等于空的時候,先遍歷自身節點, 再遍歷左子樹節點, 最后遍歷右子樹節點
                         callback(node); //自身
                         fn(node.left, callback); //左子樹
                         fn(node.right, callback) //右子樹
                      }
                  }
                  fn(this.root, callback)
              }
          


          中序遍歷

          //中序遍歷
              this.orderTraversal = function (callback) { //從小到大
                  callback = callback || function () {};
                  if (this.root === null) {  //傳入根節點
                      console.warn('請先初始化二叉排序樹');
                      return;
                  }
                  var fn = function (node, callback) {
                      if (node !== null) { //當前節點不等于空的時候,先遍歷左子樹節點, 再遍歷自身節點, 最后遍歷右子樹節點
                         fn(node.left, callback);  //左子樹
                         callback(node); //自身
                         fn(node.right, callback);  //右子樹 
                      }
                  }
                  fn(this.root, callback)
              }
          
          


          后序遍歷

          //后序遍歷
              this.postorderTraversal = function (callback) {
                  if (this.root === null) {  //傳入根節點
                      console.warn('Please initialize first');
                      return;
                  }
                  var fn = function (node, callback) {
                      if (node !== null) {  //當前節點不等于空的時候,先遍歷左子樹節點, 再遍歷右子樹節點, 最后遍歷自身節點
                         fn(node.left, callback); //左子樹
                         fn(node.right, callback);  //右子樹
                         callback(node);  //自身
                      }
                  }
                  fn(this.root, callback)
              }
          


          3.查找最小值

             this.min = function () {  //查找最小值就一直往左邊查找就行了,直到左邊沒有節點為止,那就證明已經到最小值了
                 var fn = function (node) {
                     if (node == null) {  //傳入根節點
                         console.warn('請先初始化二叉排序樹');
                         return null;
                     }
                     if (node.left) { //查找當前左子樹有沒有節點, 有點話繼續遞歸查找該左節點存不存在左節點
                         return fn(node.left);
                     }else{ //直到當前節點不在存在左節點,證明取到最小值了
                         return node;
                     }
                 }
                 return fn(this.root)   
             }
          


          4.查找最大值

             //查找最大值
             this.max = function () {  //跟查找最小值一樣,  查找最大值就一直往右邊查找就行了
                 var fn = function (node) {
                     if (node == null) {  //傳入根節點
                         console.warn('請先初始化二叉排序樹');
                         return null;
                     }
                     if (node.right) { 
                         return fn(node.right);
                     }else{
                         return node;
                     }
                 }
                 return fn(this.root) 
             }
          


          5.刪除節點

          //刪除節點
              this.remove = function (key) {
                  var fn = function (node, key) {
                      if (node === null) {  //傳入初始節點
                          console.warn('請先初始化二叉排序樹');
                          return null;
                      }
                      if (node.key > key) { //初始節點的值大于我要刪除節點的值, 說明我要刪除的節點在初始節點的左邊
                          node.left = fn(node.left, key) //遞歸一直尋找左邊的子節點,直到找到null 為止
                          return node;
                      }else if (node.key < key) {//初始節點的值小于我要刪除節點的值, 說明我要刪除的節點在初始節點的右邊
                          node.right = fn(node.right, key);
                          return node;
                      }else { //當前節點的值等于我要刪除節點的值,說明找到要刪除的節點了
          
                          //當前節點的左右兩邊分支都為空時,直接把當前節點置為null,返回出去
                          if (node.left === null && node.right === null) { 
                              node = null;
                              return node;
                          }
          
                          //當前節點只有左邊為空時, 直接引入右邊的分支替換成當前分支
                          if (node.left === null) { 
                              node = node.right;
                              return node;
                          }
          
                          //當前節點只有右邊為空時, 直接引入左邊的分支替換成當前分支
                          if (node.right == null) {  
                              node = node.left;
                              return node;
                          }
          
                          //當左右兩邊節點都不為空時, 就需要找一個值來替換當前的值, 為了結構的完整性,最好是大于左邊的值,
                          //而且小于右邊的, 這個值的最佳選擇就是當前節點右邊的最小值, 這樣就能比左邊的大,  比右邊的小
          
                          //去右邊尋找最小值, 而且最小值應該在左子樹上
                          var minNode = rightMinNode(node.right);
          
                          // 那我們就要刪除右邊最小值的那個分支, 然后把值賦值到當前節點上
          
                          fn(node, minNode.key) //執行右邊最小值刪除操作
          
                          node.key = minNode.key
                          return node;
                      }
                  }
                  var rightMinNode = function (node) {
                      if (node.left === null) { //如果第一個右子樹的左子樹上為空的話, 那他就是最小值, 如果存在那就往左子樹上在進行查詢,知道左子樹為null時, 那就是最小值
                          return node;
                      }
                      return rightMinNode(node.left)
                  }
                  fn(this.root, key)
              }

          JS實現二叉排序樹


          站長推薦

          1.阿里云: 本站目前使用的是阿里云主機,安全/可靠/穩定。點擊領取2000元代金券、了解最新阿里云產品的各種優惠活動點擊進入

          2.騰訊云: 提供云服務器、云數據庫、云存儲、視頻與CDN、域名等服務。騰訊云各類產品的最新活動,優惠券領取點擊進入

          3.廣告聯盟: 整理了目前主流的廣告聯盟平臺,如果你有流量,可以作為參考選擇適合你的平臺點擊進入

          鏈接: http://www.modern-decoration.com.cn/article/detial/309

          字典樹的應用

          Ignatius最近遇到一個難題,老師交給他很多單詞(只有小寫字母組成,不會有重復的單詞出現),現在老師要他統計出以某個字符串為前綴的單詞數量(單詞本身也是自己的前綴).

          關于Element UI tree組件 懶加載的更新操作

          近期根據需求,要做一個懶加載的組織樹,并且可以編輯組織樹。但是編輯成功之后,卻無法進行實時更新。一開始想到了很多解決方案,也在網上參考了很多方案,但是都有種種不足。遂查閱了ElementUi的tree組件源代碼。

          用 JavaScript 實現單詞查找樹

          對于搜索字符串的需求,在最壞的情況下,二叉搜索樹的時間復雜度可能為 O(n),“n” 是二叉樹中存儲的字符串的總數量。所以為了在最佳時間內搜索字符串,需要一種性能更好的數據結構

          JS樹結構操作:查找、遍歷、樹結構和列表結構相互轉換

          經常有同學問樹結構的相關操作,也寫了很多次,在這里總結一下JS樹形結構一些操作的實現思路,并給出了簡潔易懂的代碼實現。本文內容結構大概如下:

          快速實現一個簡單可復用可擴展的Vue樹組件

          大概因為平時工作項目的原因,寫了很多次樹形組件,越寫越覺得可以寫得更簡單并且更具有復用性、擴展性。樹組件的應用場景很多,比如一篇文章的目錄、一個公司部門組織情況、思維導圖等,其實都可以用樹形結構來描述

          js將扁平結構數據轉換為樹形結構

          最近項目又頻繁需要對扁平結構進行樹形轉換,這個算法從我最早接觸的時候使用了遞歸,到現在的單次循環完成,簡單記錄一下算法的演變,算是對樹形算法的一個簡單記錄,這種類型的算法在項目中的使用挺多的

          Js二叉樹的遍歷

          二叉樹是每個結點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”(left subtree)和“右子樹”(right subtree)。二叉樹常被用于實現二叉查找樹和二叉堆。

          vue遞歸組件:樹形控件

          在編寫樹形組件時遇到的問題:組件如何才能遞歸調用?遞歸組件點擊事件如何傳遞?組件目錄及數據結構;在組件模板內調用自身必須明確定義組件的name屬性,并且遞歸調用時組件名稱就是name屬性

          Js算法之自平衡樹

          節點的高度和平衡因子;節點高度:從節點到任意子節點的彼岸的最大值。這個相對來說容易理解。那么獲得節點高度的代碼實現如下:平衡因子:每個節點左子樹高度和右子樹高度的差值。該值為0 、 -1、 1 時則為正常值

          js 實現 list轉換成tree(數組到樹)

          JS 將有父子關系的平行數組轉換成樹形數據:方法一:雙重遍歷,一次遍歷parentId,一次遍歷id == parendId;該方法應該能很容易被想到,實現起來也一步一步可以摸索出來;

          內容以共享、參考、研究為目的,不存在任何商業目的。其版權屬原作者所有,如有侵權或違規,請與小編聯系!情況屬實本人將予以刪除!

          文章投稿關于web前端網站點搜索站長推薦網站地圖站長QQ:522607023

          小程序專欄: 土味情話心理測試腦筋急轉彎幽默笑話段子句子語錄成語大全運營推廣

          国产精品高清视频免费 - 视频 - 在线观看 - 影视资讯 - 唯爱网