本篇文章給大家分享的是有關(guān)關(guān)于JavaScript二叉樹(shù)的詳細(xì)介紹，小編覺(jué)得挺實(shí)用的，因此分享給大家學(xué)習(xí)，希望大家閱讀完這篇文章后可以有所收獲，話不多說(shuō)，跟著小編一起來(lái)看看吧。

為馬關(guān)等地區(qū)用戶提供了全套網(wǎng)頁(yè)設(shè)計(jì)制作服務(wù)，及馬關(guān)網(wǎng)站建設(shè)行業(yè)解決方案。主營(yíng)業(yè)務(wù)為網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)、馬關(guān)網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠(chéng)的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長(zhǎng)期合作。這樣，我們也可以走得更遠(yuǎn)！

可能有一部分人沒(méi)有讀過(guò)我上一篇寫(xiě)的二叉堆，所以這里把二叉樹(shù)的基本概念復(fù)制過(guò)來(lái)了，如果讀過(guò)的人可以忽略前面針對(duì)二叉樹(shù)基本概念的介紹，另外如果對(duì)鏈表數(shù)據(jù)結(jié)構(gòu)不清楚的最好先看一下本人之前寫(xiě)的js數(shù)據(jù)結(jié)構(gòu)-鏈表

二叉樹(shù)

二叉樹(shù)(Binary Tree)是一種樹(shù)形結(jié)構(gòu)，它的特點(diǎn)是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支節(jié)點(diǎn)，一棵二叉樹(shù)通常由根節(jié)點(diǎn)，分支節(jié)點(diǎn)，葉子節(jié)點(diǎn)組成。而每個(gè)分支節(jié)點(diǎn)也常常被稱作為一棵子樹(shù)。

• 根節(jié)點(diǎn)：二叉樹(shù)最頂層的節(jié)點(diǎn)

• 分支節(jié)點(diǎn)：除了根節(jié)點(diǎn)以外且擁有葉子節(jié)點(diǎn)

• 葉子節(jié)點(diǎn)：除了自身，沒(méi)有其他子節(jié)點(diǎn)

常用術(shù)語(yǔ)
在二叉樹(shù)中，我們常常還會(huì)用父節(jié)點(diǎn)和子節(jié)點(diǎn)來(lái)描述，比如圖中2為6和3的父節(jié)點(diǎn)，反之6和3是2子節(jié)點(diǎn)

二叉樹(shù)的三個(gè)性質(zhì)

1. 在二叉樹(shù)的第i層上，至多有2^i-1個(gè)節(jié)點(diǎn)

• i=1時(shí)，只有一個(gè)根節(jié)點(diǎn)，2^(i-1) = 2^0 = 1

2. 深度為k的二叉樹(shù)至多有2^k-1個(gè)節(jié)點(diǎn)

• i=2時(shí)，2^k-1 = 2^2 - 1 = 3個(gè)節(jié)點(diǎn)

3. 對(duì)任何一棵二叉樹(shù)T，如果總結(jié)點(diǎn)數(shù)為n0，度為2(子樹(shù)數(shù)目為2)的節(jié)點(diǎn)數(shù)為n2,則n0=n2+1

樹(shù)和二叉樹(shù)的三個(gè)主要差別

• 樹(shù)的節(jié)點(diǎn)個(gè)數(shù)至少為1，而二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)可以為0

• 樹(shù)中節(jié)點(diǎn)的大度數(shù)(節(jié)點(diǎn)數(shù)量)沒(méi)有限制,而二叉樹(shù)的節(jié)點(diǎn)的大度數(shù)為2

• 樹(shù)的節(jié)點(diǎn)沒(méi)有左右之分，而二叉樹(shù)的節(jié)點(diǎn)有左右之分

二叉樹(shù)分類(lèi)

二叉樹(shù)分為完全二叉樹(shù)(complete binary tree)和滿二叉樹(shù)(full binary tree)

• 滿二叉樹(shù)：一棵深度為k且有2^k - 1個(gè)節(jié)點(diǎn)的二叉樹(shù)稱為滿二叉樹(shù)

• 完全二叉樹(shù)：完全二叉樹(shù)是指最后一層左邊是滿的，右邊可能滿也可能不滿，然后其余層都是滿的二叉樹(shù)稱為完全二叉樹(shù)(滿二叉樹(shù)也是一種完全二叉樹(shù))

二叉搜索樹(shù)

二叉搜索樹(shù)滿足以下的幾個(gè)性質(zhì)：

• 若任意節(jié)點(diǎn)的左子樹(shù)不空，則左子樹(shù)上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；

• 若任意節(jié)點(diǎn)的右子樹(shù)不空，則右子樹(shù)上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；

• 任意節(jié)點(diǎn)的左、右子樹(shù)也需要滿足左邊小右邊大的性質(zhì)

我們來(lái)舉個(gè)例子來(lái)深入理解以下

一組數(shù)據(jù)：12,4,18,1,8,16,20
由下圖可以看出，左邊的圖滿足了二叉樹(shù)的性質(zhì)，它的每個(gè)左子節(jié)點(diǎn)都小于父節(jié)點(diǎn)，右子節(jié)點(diǎn)大于其父節(jié)點(diǎn)，同時(shí)左子樹(shù)的節(jié)點(diǎn)都小于根節(jié)點(diǎn)，右子樹(shù)的節(jié)點(diǎn)都大于根節(jié)點(diǎn)

二叉搜索樹(shù)主要的幾個(gè)操作：

• 查找（search）

• 插入（insert）

• 遍歷（transverse）

二叉樹(shù)搜索樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

通過(guò)下圖，可以知道二叉搜索樹(shù)的節(jié)點(diǎn)通常包含4個(gè)域，數(shù)據(jù)元素，分別指向其左，右節(jié)點(diǎn)的指針和一個(gè)指向父節(jié)點(diǎn)的指針?biāo)鶚?gòu)成，一般把這種存儲(chǔ)結(jié)構(gòu)稱為三叉鏈表。

用代碼初始化一個(gè)二叉搜索樹(shù)的結(jié)點(diǎn)：

• 一個(gè)指向父親節(jié)點(diǎn)的指針 parent

• 一個(gè)指向左節(jié)點(diǎn)的指針 left

• 一個(gè)指向右節(jié)點(diǎn)的指針 right

• 一個(gè)數(shù)據(jù)元素，里面可以是一個(gè)key和value

    class BinaryTreeNode {
        constructor(key, value){
            this.parent = null;
            this.left = null;
            this.right = null;
            this.key = key;
            this.value = value;
        }
    }

接著我們?cè)儆么a去初始化一個(gè)二叉搜索樹(shù)

• 在二叉搜索樹(shù)中我們會(huì)維護(hù)一個(gè)root指針，這個(gè)就相當(dāng)于鏈表中的head指針，在沒(méi)有任何節(jié)點(diǎn)插入的時(shí)候它指向空，在有節(jié)點(diǎn)插入以后它指向根節(jié)點(diǎn)。

    class BinarySearchTree {
        constructor() {
            this.root = null;
        }
    }

創(chuàng)建節(jié)點(diǎn)

    static createNode(key, value) {
        return new BinarySearchTree(key, value);
    }

插入操作

看下面這張圖，13是我們要插入的節(jié)點(diǎn)，它插入的具體步驟：

1. 跟根節(jié)點(diǎn)12做比較，比12大，所以我們確定了，這個(gè)節(jié)點(diǎn)是往右子樹(shù)插入的

2. 而根節(jié)點(diǎn)的右邊已經(jīng)有節(jié)點(diǎn)，那么跟這個(gè)節(jié)點(diǎn)18做比較，結(jié)果小于18所以往18的左節(jié)點(diǎn)找位置

3. 而18的左節(jié)點(diǎn)也已經(jīng)有節(jié)點(diǎn)了，所以繼續(xù)跟這個(gè)節(jié)點(diǎn)做比較，結(jié)果小于16

4. 剛好16的左節(jié)點(diǎn)是空的(left=null)，所以13這個(gè)節(jié)點(diǎn)就插入到了16的左節(jié)點(diǎn)

通過(guò)上面的描述，我們來(lái)看看代碼是怎么寫(xiě)的

• 定義兩個(gè)指針，分別是p和tail，最初都指向root，p是用來(lái)指向要插入的位置的父節(jié)點(diǎn)的指針，而tail是用來(lái)查找插入位置的，所以最后它會(huì)指向null，用上圖舉個(gè)例子，p最后指向了6這個(gè)節(jié)點(diǎn)，而tail最后指向了null（tail為null則說(shuō)明已經(jīng)找到了要插入的位置）

• 循環(huán)，tail根據(jù)我們上面分析的一步一步往下找位置插入，如果比當(dāng)前節(jié)點(diǎn)小就往左找，大則往右找，一直到tail找到一個(gè)空位置也就是null

• 如果當(dāng)前的root為null，則說(shuō)明當(dāng)前結(jié)構(gòu)中并沒(méi)有節(jié)點(diǎn)，所以插入的第一個(gè)節(jié)點(diǎn)直接為跟節(jié)點(diǎn)，即this.root = node

• 將插入后的節(jié)點(diǎn)的parent指針指向父節(jié)點(diǎn)

    insert(node){
        let p = this.root;
        let tail = this.root;
        
        // 循環(huán)遍歷，去找到對(duì)應(yīng)的位置
       while(tail) {
            p = tail;
            // 要插入的節(jié)點(diǎn)key比當(dāng)前節(jié)點(diǎn)小
            if (node.key < tail.key){
                tail.left = tail.left;
            }
            // 要插入的節(jié)點(diǎn)key比當(dāng)前節(jié)點(diǎn)大
            else {
                tail.right = tail.right;
            }
        }
        
        // 沒(méi)有根節(jié)點(diǎn)，則直接作為根節(jié)點(diǎn)插入
        if(!p) {
            this.root = node;
            return;
        }
        
        // p是最后一個(gè)節(jié)點(diǎn)，也就是我們要插入的位置的父節(jié)點(diǎn)
        // 比父節(jié)點(diǎn)大則往右邊插入
        if(p.key < node.key){
            p.right = node;
        }
        // 比父節(jié)點(diǎn)小則往左邊插入
        else {
            p.left = node;
        }
        
        // 指向父節(jié)點(diǎn)
        node.parent = p;

    }

查找

查找就很簡(jiǎn)單了，其實(shí)和插入差多，都是去別叫左右節(jié)點(diǎn)的大小，然后往下找

• 如果root = null, 則二叉樹(shù)中沒(méi)有任何節(jié)點(diǎn)，直接return，或者報(bào)個(gè)錯(cuò)什么的。

• 循環(huán)查找

    search(key) {
        let p = this.root;
        if(!p) {
            return;
        }
        
       while(p && p.key !== key){
            if(p.key<key){
                p = p.right;
            }else{
                p = p.left;
            }
        }
        
        return p;
    }

遍歷

• 中序遍歷(inorder)：先遍歷左節(jié)點(diǎn)，再遍歷自己，最后遍歷右節(jié)點(diǎn)，輸出的剛好是有序的列表

• 前序遍歷(preorder)：先自己，再遍歷左節(jié)點(diǎn)，最后遍歷右節(jié)點(diǎn)

• 后序遍歷(postorder)：先左節(jié)點(diǎn)，再右節(jié)點(diǎn)，最后自己

最常用的一般是中序遍歷，因?yàn)橹行虮闅v可以得到一個(gè)已經(jīng)排好序的列表，這也是為什么會(huì)用二叉搜索樹(shù)排序的原因

根據(jù)上面對(duì)中序遍歷的解釋，那么代碼就變的很簡(jiǎn)單，就是一個(gè)遞歸的過(guò)程，遞歸停止的條件就是節(jié)點(diǎn)為null

• 先遍歷左節(jié)點(diǎn)-->yield* this._transverse(node.left)

• 遍歷自己 --> yield* node

• 遍歷左節(jié)點(diǎn) --> yield* this._transverse(node.right)

    transverse() {
        return this._transverse(this.root);
    }
    
    *_transverse(node){
        if(!node){
            return;
        }
        yield* this._transverse(node.left);
        yield node;
        yield* this._transverse(node.right)
    }

看上面這張圖，我們簡(jiǎn)化的來(lái)看一下，先訪問(wèn)左節(jié)點(diǎn)4，再自己12，然后右節(jié)點(diǎn)18，這樣輸出的就剛好是一個(gè)12，4，8

補(bǔ)充：這個(gè)地方用了generater，所以返回的一個(gè)迭代器。可以通過(guò)下面這種方式得到一個(gè)有序的數(shù)組，這里的前提就當(dāng)是已經(jīng)有插入的節(jié)點(diǎn)了

   const tree = new BinaryTree();
   //...中間省略插入過(guò)程
    
   // 這樣就返回了一個(gè)有序的數(shù)組 
   var arr = [...tree.transverse()].map(item=>item.key);

完整代碼

class BinaryTreeNode {
  constructor(key, value) {
    // 指向父節(jié)點(diǎn)
    this.p = null;

    // 左節(jié)點(diǎn)
    this.left = null;

    // 右節(jié)點(diǎn)
    this.right = null;

    // 鍵
    this.key = key;

    // 值
    this.value = value;
  }
}

class BinaryTree {
  constructor() {
    this.root = null;
  }

  static createNode(key, value) {
    return new BinaryTreeNode(key, value);
  }

  search(key) {
    let p = this.root;
    if (!p) {
      return;
    }

   while (p && p.key !== key) {
      if (p.key < key) {
        p = p.right;
      } else {
        p = p.left;
      }
    }

    return p;
  }

  insert(node) {
    // 尾指針的父節(jié)點(diǎn)指針
    let p = this.root;

    // 尾指針
    let tail = this.root;

   while (tail) {
      p = tail;
      if (node.key < tail.key) {
        tail = tail.left;
      } else {
        tail = tail.right;
      }
    }

    if (!p) {
      this.root = node;
      return;
    }

    // 插入
    if (p.key < node.key) {
      p.right = node;
    } else {
      p.left = node;
    }

    node.p = p;
  }

  transverse() {
    return this.__transverse(this.root);
  }

  *__transverse(node) {
    if (!node) {
      return;
    }
    yield* this.__transverse(node.left);
    yield node;
    yield* this.__transverse(node.right);
  }
}

總結(jié)

二叉查找樹(shù)就講完了哈，其實(shí)這個(gè)和鏈表很像的，還是操作那么幾個(gè)指針，既然叫查找樹(shù)了，它主要還是用來(lái)左一些搜索，還有就是排序了，另外補(bǔ)充一下，二叉查找樹(shù)里找大值和最小值也很方便是不是，如果你大致讀懂了的話。

以上就是關(guān)于JavaScript二叉樹(shù)的詳細(xì)介紹，小編相信有部分知識(shí)點(diǎn)可能是我們?nèi)粘９ぷ鲿?huì)見(jiàn)到或用到的。希望你能通過(guò)這篇文章學(xué)到更多知識(shí)。更多詳情敬請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

網(wǎng)頁(yè)題目：關(guān)于JavaScript二叉樹(shù)的詳細(xì)介紹-創(chuàng)新互聯(lián)
分享路徑：http://www.rwnh.cn/article48/pihep.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、網(wǎng)站設(shè)計(jì)公司、服務(wù)器托管、營(yíng)銷(xiāo)型網(wǎng)站建設(shè)、企業(yè)網(wǎng)站制作、網(wǎng)站設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)