實作非平衡二叉樹的單旋：
<!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 =https://www.cnblogs.com/lanshanxiao/p/ 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>
非平衡二叉樹的單旋
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/36579.html
標籤：其他