用JS實現數據結構----排序二叉樹

ispring 發布于2019-08-23 11:00 / 1940人閱讀

摘要：代碼實現創建一個排序二叉樹節點類根節點插入節點以上便是創建排序二叉樹的實現方式重點在于插入節點的具體實現，即注釋的代碼片段。

排序二叉樹

如上圖為典型的排序二叉樹，左孩子的值比節點的值小，右孩子的值比節點的值大，關于具體的樹的定義及二叉樹的定義可以百度或查閱相關資料。

排序二叉樹的創建

創建原理
排序二叉樹的創建原理與排序二叉樹的定義一致，即左孩子的值比當前節點的值小，右孩子的值比當前節點的值大。

代碼實現




    
    
    binary-tree

以上便是創建排序二叉樹的實現方式：
重點在于插入節點的具體實現，即注釋1的代碼片段。
其中比較難理解的點在于遞歸是如何執行，
取當前的節點為{key: 1, left:null, right:null},則當前樹如下圖：

對該樹進行插入

           var insertNode = function(node, newNode) {
                if(node !== null) {
                    if(newNode.key < node.key) {
                        insertNode(node.left, newNode)
                        if(node.left == null) {
                            node.left = newNode
                        }
                    }else{
                        insertNode(node.right, newNode)
                        if(node.right == null) {
                            node.right = newNode
                        }
                    }
                }

                return null
            }

首先由根節點8出發，進入node的key為8的棧內1比根節點8要小，進入遞歸，即進入到了node的key為3的棧內，如下所示：

        3
   -----------------
        8
  --------------------------

當前的值比3小再進入3的左孩子null的棧內

    
        null
    ------------
        3
   -----------------
        8
  --------------------------

由于null的棧內，node為null，立即退出當前棧，返回至node的key為3的棧，發現左孩子為null，則將key為1的node變成key為3的node的左孩子，同時退出3的棧，返回至8的棧，8的棧左孩子不null,不做任何操作，知道當前方法執行完畢，跳出8的棧，返回至方法所在的執行環境的棧，節點插入完畢，再進行下一個節點的插入，操作則同上。以上的解釋，如果配合上瀏覽器的斷點調試，食用更佳，更好理解程序的整個執行過程。

當所有節點插入完畢之后，該排序二叉樹也創建完畢。

二叉樹創建完畢之后則可對二叉樹進行相關的操作（遍歷，查找，節點刪除等）【待續】

GPU云服務器云服務器二叉樹排序樹規則實現二叉樹 JS二叉樹遍歷 js怎么建二叉樹

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

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

數據結構以及相關排序

摘要：桶排序與計數排序的區別桶排序中一個桶可以放一個范圍內的多個數據，在各個桶中又可以用其他方法排序，其快速之處在于只用對比同一個桶內的數字而無需與其他桶的數字作對比。與計數排序相比，桶排序需要作二次對比，但可省略桶的個數。哈希表（Hash Table）所有符合鍵值對即key-value的結構就是哈希。數組其實也是一種哈希。計數排序（復雜度(n+max)）無法統計負數和小數，需要一個...

Brenner 2019-08-23 12:20 評論0 收藏0
使用javascript實現排序二叉樹（1）

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

Caicloud 2019-08-23 11:29 評論0 收藏0
js數據結構-二叉樹（二叉堆）

摘要：二叉樹二叉樹是一種樹形結構，它的特點是每個節點最多只有兩個分支節點，一棵二叉樹通常由根節點，分支節點，葉子節點組成。二叉樹二叉樹(Binary Tree)是一種樹形結構，它的特點是每個節點最多只有兩個分支節點，一棵二叉樹通常由根節點，分支節點，葉子節點組成。而每個分支節點也常常被稱作為一棵子樹。 showImg(https://segmentfault.com/img/bVbmEd...

ningwang 2019-08-23 14:29 評論0 收藏0
js數據結構-二叉樹（二叉搜索樹）

摘要：前言可能有一部分人沒有讀過我上一篇寫的二叉堆，所以這里把二叉樹的基本概念復制過來了，如果讀過的人可以忽略前面針對二叉樹基本概念的介紹，另外如果對鏈表數據結構不清楚的最好先看一下本人之前寫的數據結構鏈表二叉樹二叉樹是一種樹形結構，它的特點是前言可能有一部分人沒有讀過我上一篇寫的二叉堆，所以這里把二叉樹的基本概念復制過來了，如果讀過的人可以忽略前面針對二叉樹基本概念的介紹，另外如果對鏈...

codeKK 2019-08-23 14:34 評論0 收藏0