《学习JavaScript数据结构与算法》（第8章）（平衡二叉树代码实现）

isLishude 发布于2019-08-26 10:37 / 2181人阅读

摘要：平衡二叉树代码实现根节点插入节点树为空树不为空比较小于往左走大于往右走空树树非空自平衡树插入新节点向左走向左子树拆入新节点，且节点的值小于其左子节点时，应该进行旋转。

平衡二叉树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云服务器平衡二叉树平衡二叉树课程设计二叉树算法实现二叉树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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