2048
登录
没  有  难  学  的  前  端
登 录
×
<返回上一级

13.实现非平衡二叉树的单旋(左旋和右旋)代码实现JavaScript版

前端-数据结构与算法(javascript版)作者:苦咖啡

实现非平衡二叉树的单旋:

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        //旋转的一些概念:
        //旋转节点:不平衡的节点为旋转节点
        //新根:旋转之后成为根节点的节点
        //变化分支:父级节点变化的那个分支
        //不变分支:父级节点不变的那个分支

        //左单旋时:
        //旋转节点:不平衡的节点
        //新根:右子树的根节点
        //变化分支:右子树的左子树
        //不变分支:右子树的右子树

        //左单旋时:
        //旋转节点:不平衡的节点
        //新根:左子树的根节点
        //变化分支:左子树的右子树
        //不变分支:左子树的左子树




        function Node(value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }

        var node1 = new Node(1);
        var node2 = new Node(2);
        var node3 = new Node(3);
        var node4 = new Node(4);

        node4.left = node2;
        node2.left = node1;
        node2.right = node3;

        //判断二叉树是否平衡
        function isBalance(root) {
            if (root == null) return true;
            //获取左右的深度
            var leftDeep = getDeep(root.left);
            var rightDeep = getDeep(root.right);
            //若左右深度相差大于1,则不是平衡树
            if (Math.abs(leftDeep - rightDeep) > 1) {
                return false;
            } else {
                //判断左右子树是否平衡
                return isBalance(root.left) && isBalance(root.right);
            }
        }

        //获取树的深度
        function getDeep(root) {
            if (root == null) return 0;
            var leftDeep = getDeep(root.left);
            var rightDeep = getDeep(root.right);
            return Math.max(leftDeep, rightDeep) + 1; //取两个深度中最大的一个,加上自身
        }

        //平衡二叉树操作,用的是后序遍历
        function change(root) { //返回平衡之后的根节点
            if(isBalance(root)) return root;
            if(root.left != null) root.left = change(root.left);
            if(root.right != null) root.right = change(root.right);
            var leftDeep = getDeep(root.left);
            var rightDeep = getDeep(root.right);
            if(Math.abs(leftDeep - rightDeep) < 2){//树是平衡的
                return true;
            }else if(leftDeep > rightDeep){//左深右浅,需要右旋
                return rightRotate(root);
            }else if(leftDeep < rightDeep){//左浅右深,需要左旋
                return leftRotate(root);
            }
        }

        function rightRotate(root) { //右旋
            //找到新根
            var newRoot = root.left;
            //找到变化分支
            var changeTree = root.left.right;
            //将变化分支加入到当前旋转节点的左子树
            root.left = changeTree;
            //将当前旋转节点加入到新根的右子树
            newRoot.right = root;
            //返回新的根节点
            return newRoot;
        }

        function leftRotate(root) { //左旋
            //找到新根
            var newRoot = root.right;
            //找到变化分支
            var changeTree = root.right.left;
            //将变化分支加入到当前旋转节点的右子树
            root.right = changeTree;
            //将当前旋转节点加入到新根的左子树
            newRoot.left = root;
            //返回新的根节点
            return newRoot;
        }

        console.log(isBalance(node4));
        var newRoot = change(node4);
        console.log(isBalance(newRoot));
        console.log(newRoot);
    </script>
</body>

</html>
非平衡二叉树的单旋

 

本文来源于网络:查看 >
« 上一篇:5大主流浏览器内核
» 下一篇:vue 项目 国际化
评论
点击刷新
评论
相关博文
×添加代码片段