点击刷新
<!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);
var node5 = new Node(5);
var node6 = new Node(6);
node6.left = node3;
node3.left = node2;
node2.left = node1;
node3.right = node4;
node4.right = node5;
function isBalance(root){//判断二叉树是否平衡
if(root == null) return true;
var leftDeep = getDeep(root.left);
var rightDeep = getDeep(root.right);
if(Math.abs(leftDeep - rightDeep) > 1){//左右深度相差大于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;//左右子树深度最大的值 + 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 root;
}else if(leftDeep > rightDeep){//左深右浅，要右旋
var changeTreeDeep = getDeep(root.left.right);//变化分支的深度
var noChangeTreeDeep = getDeep(root.left.left);//不变化分支的深度
if(changeTreeDeep > noChangeTreeDeep ){//变化分支深度 大于 不变化分支深度，要将左子树先进行左旋
root.left = leftRotate(root.left);
}
var newRoot = rightRotate(root);//右旋,右旋是为了减小左子树深度,但是右旋后可能增加右子树深度
newRoot = change(newRoot);//右旋后可能会导致树不平衡，所以再次平衡
return newRoot;
}else{//左浅右深，要左旋
var changeTreeDeep = getDeep(root.right.left);//变化分支的深度
var noChangeTreeDeep = getDeep(root.right.right);//不变化分支的深度
if(changeTreeDeep > noChangeTreeDeep){//变化分支深度 大于 不变化分支深度，要将右子树先进行右旋
root.right = rightRotate(root.right);
}
var newRoot = leftRotate(root);//左旋,左旋是为了减小右子树深度,但是左旋后可能增加左子树深度
newRoot = change(newRoot);//左旋后可能会导致树不平衡，所以再次平衡
return newRoot;
}
}
//左旋
function leftRotate(root){
//找到新根
var newRoot = root.right;
//找到变化的分支
var changeTree = root.right.left;
//将当前节点赋值到新根的左节点
newRoot.left = root;
//将变化分支赋值到当前节点的右节点
root.right = changeTree;
return newRoot;//返回新根
}
//右旋
function rightRotate(root){
//找到新根
var newRoot = root.left;
//找到变化的分支
var changeTree = root.left.right;
//将当前节点赋值到新根的右节点
newRoot.right = root;
//将变化分支赋值到当前节点的左节点
root.left = changeTree;
return newRoot;//返回新根
}
console.log(isBalance(node6));
var newRoot = change(node6);
console.log(isBalance(newRoot));
console.log(newRoot);
</script>
</body>
</html>
© 著作权归作者所有
举报
发表评论
0/200
