《學習JavaScript數據結構與算法》（第8章）（平衡二叉樹代碼實現）

isLishude 發布于2019-08-26 10:37 / 2185人閱讀

摘要：平衡二叉樹代碼實現根節點插入節點樹為空樹不為空比較小于往左走大于往右走空樹樹非空自平衡樹插入新節點向左走向左子樹拆入新節點，且節點的值小于其左子節點時，應該進行旋轉。

平衡二叉樹JS代碼實現

var Tree = function() {
    var Node = function(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
    var root = null;    //根節點  
    /*
    插入節點：
    1、樹為空
    2、樹不為空 -> 比較（小于 -> 往左走；大于 -> 往右走）
    */ 
    this.insert = function(value) {
        var newNode = new Node(value);
        if(root == null) { //空樹          
            root = newNode;
        }else{//樹非空           
            insertNode(root, newNode);
        }
    };

    //自平衡樹插入新節點
    var insertNode = function(node,newNode) {
        if(node == null) {
            node = newNode;
        //向左走(向左子樹拆入新節點，且節點的值小于其左子節點時，應該進行LL旋轉。否則，進行LR旋轉)
        }else if(newNode.value < node.value) {
            node.left = insertNode(node.left, newNode);
            if(node.left == null) {
                node.left = newNode;
                if(heightNode(node.left) - heightNode(node.right) > 1) {
                    if(newNode.value < node.left.value) {
                        node = rotationLL(node);
                    }else{
                        node = rotationLR(node);
                    }
                }
            }else if(node.left !== null){
                if(heightNode(node.left) - heightNode(node.right) > 1) {
                    if(newNode.value < node.left.value) {
                        node = rotationLL(node);
                    }else{
                        node = rotationLR(node);
                    }
                }
            }
        //向右走(向右子樹拆入新節點，且節點的值大于其右子節點時，應該進行RR旋轉。否則，進行RL旋轉)
        }else if(newNode.value > node.value) {
            node.right = insertNode(node.right, newNode);
            if(node.right == null) {
                node.right = newNode;
                if(heightNode(node.right) - heightNode(node.left) > 1) {
                    if(newNode.value > node.right.value) {
                        node = rotationRR(node);
                    }else{
                        node = rotationRL(node);
                    }
                }
            }else if(node.right !== null) {
                if(heightNode(node.right) - heightNode(node.left) > 1) {
                    if(newNode.value > node.right.value) {
                        node = rotationRR(node);
                    }else{
                        node = rotationRL(node);
                    }
                }
            }
        }
        return node;
    };
    var heightNode = function(node) {
        if(node === null) {
            return -1;
        }else{
            return Math.max(heightNode(node.left), heightNode(node.right)) + 1;
        }
    };
    //RR向左的單旋轉
    var rotationRR = function(node) {
        var tmp = node.right;
        node.right = tmp.left;
        tmp.left = node;
        return tmp;
    };
    //LL向右的單旋轉
    var rotationLL = function(node) {
        var tmp = node.left;
        node.left = tmp.right;
        tmp.right = node;
        return tmp;
    };
    //LR向右的雙旋轉
    var rotationLR = function(node) {
        node.left = rotationRR(node.left);
        return rotationLL(node);
    }
    //RL向左的雙旋轉
    var rotationRL = function(node) {
        node.right = rotationLL(node.right);
        return rotationRR(node);
    };

    //遍歷節點
    this.traverse = function(callback) {
        traverse(root, callback);
    };
    var traverse = function(node, callback) {
        if(node == null) return;
        //（后續遍歷）左右中；（中序遍歷）左中右；（前序遍歷）中左右
        traverse(node.left, callback);
        traverse(node.right, callback);
        callback(node.value);
    };
    
    //顯示樹
    this.getRoot = function() {
        return root;
    };
}

測試代碼：

var t = new Tree;
var print = function(value) {
    console.log("value -",value)   
};

t.insert(11);
t.insert(8);
t.insert(4);
t.insert(9);
t.traverse(print);

云服務器 GPU云服務器平衡二叉樹平衡二叉樹課程設計二叉樹算法實現二叉樹

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

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

數據結構與算法:二叉樹算法

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

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

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

singerye 2019-08-26 10:09 評論0 收藏0
一文掌握關于Java數據結構所有知識點（歡迎一起完善）

摘要：是棧，它繼承于。滿二叉樹除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。沒有鍵值相等的節點。這是數據庫選用樹的最主要原因。在我們學習Java的時候，很多人會面臨我不知道繼續學什么或者面試會問什么的尷尬情況（我本人之前就很迷茫）。所以，我決定通過這個開源平臺來幫助一些有需要的人，通過下面的內容，你會掌握系統的Java學習以及面試的相關知識。本來是想通過Gitbook的...

keithxiaoy 2019-08-15 15:54 評論0 收藏0
學習javascript數據結構(四)——樹

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

Dean 2019-08-20 13:47 評論0 收藏0
學習JavaScript數據結構與算法 — AVL樹

摘要：可以看到，一次左單旋將右側子樹的高度減小了，而左側子樹的高度增加了。如圖，對進行右單旋，需要左子樹的右子樹的高度小于等于左子樹的高度，否則不能達到平衡的效果，只是把不平衡性從左邊轉移到了右邊。 AVL樹普通二叉搜索樹可能出現一條分支有多層，而其他分支卻只有幾層的情況，如圖1所示，這會導致添加、移除和搜索樹具有性能問題。因此提出了自平衡二叉樹的概念，AVL樹（阿德爾森-維爾斯和蘭迪斯樹...

impig33 2019-08-21 11:31 評論0 收藏0