資訊專欄INFORMATION COLUMN
摘要：平衡二叉樹代碼實(shí)現(xiàn)根節(jié)點(diǎn)插入節(jié)點(diǎn)樹為空樹不為空比較小于往左走大于往右走空樹樹非空自平衡樹插入新節(jié)點(diǎn)向左走向左子樹拆入新節(jié)點(diǎn)，且節(jié)點(diǎn)的值小于其左子節(jié)點(diǎn)時(shí)，應(yīng)該進(jìn)行旋轉(zhuǎn)。
平衡二叉樹JS代碼實(shí)現(xiàn)
var Tree = function() {
var Node = function(value) {
this.value = value;
this.left = null;
this.right = null;
}
var root = null; //根節(jié)點(diǎn)
/*
插入節(jié)點(diǎn)：
1、樹為空
2、樹不為空 -> 比較（小于 -> 往左走；大于 -> 往右走）
*/
this.insert = function(value) {
var newNode = new Node(value);
if(root == null) { //空樹
root = newNode;
}else{//樹非空
insertNode(root, newNode);
}
};
//自平衡樹插入新節(jié)點(diǎn)
var insertNode = function(node,newNode) {
if(node == null) {
node = newNode;
//向左走(向左子樹拆入新節(jié)點(diǎn)，且節(jié)點(diǎn)的值小于其左子節(jié)點(diǎn)時(shí)，應(yīng)該進(jìn)行LL旋轉(zhuǎn)。否則，進(jìn)行LR旋轉(zhuǎn))
}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);
}
}
}
//向右走(向右子樹拆入新節(jié)點(diǎn)，且節(jié)點(diǎn)的值大于其右子節(jié)點(diǎn)時(shí)，應(yīng)該進(jìn)行RR旋轉(zhuǎn)。否則，進(jìn)行RL旋轉(zhuǎn))
}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向左的單旋轉(zhuǎn)
var rotationRR = function(node) {
var tmp = node.right;
node.right = tmp.left;
tmp.left = node;
return tmp;
};
//LL向右的單旋轉(zhuǎn)
var rotationLL = function(node) {
var tmp = node.left;
node.left = tmp.right;
tmp.right = node;
return tmp;
};
//LR向右的雙旋轉(zhuǎn)
var rotationLR = function(node) {
node.left = rotationRR(node.left);
return rotationLL(node);
}
//RL向左的雙旋轉(zhuǎn)
var rotationRL = function(node) {
node.right = rotationLL(node.right);
return rotationRR(node);
};
//遍歷節(jié)點(diǎn)
this.traverse = function(callback) {
traverse(root, callback);
};
var traverse = function(node, callback) {
if(node == null) return;
//（后續(xù)遍歷）左右中；（中序遍歷）左中右；（前序遍歷）中左右
traverse(node.left, callback);
traverse(node.right, callback);
callback(node.value);
};
//顯示樹
this.getRoot = function() {
return root;
};
}
測(cè)試代碼：
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);
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/106501.html
摘要：因此，根據(jù)題目給出的先序遍歷和中序遍歷，可以畫出二叉樹選參考數(shù)據(jù)結(jié)構(gòu)與算法描述實(shí)現(xiàn)二叉樹算法淺談數(shù)據(jù)結(jié)構(gòu)二叉樹慕課網(wǎng)實(shí)現(xiàn)二叉樹算法前端樹控件騰訊軟件開發(fā)面試題 內(nèi)容銜接上一章 數(shù)據(jù)結(jié)構(gòu)與算法:常見排序算法 內(nèi)容提要 什么是樹 - 為什么使用樹 二叉樹 二叉查找樹 紅黑樹 Ｂ、Ｂ＋樹 堆 伸展樹 樹 可以點(diǎn)擊鏈接感受下筆者用d3.js畫的tree https://codepen...
摘要：筆者寫的數(shù)據(jù)結(jié)構(gòu)與算法之美系列用的語言是，旨在入門數(shù)據(jù)結(jié)構(gòu)與算法和方便以后復(fù)習(xí)。非線性表中的樹堆是干嘛用的其數(shù)據(jù)結(jié)構(gòu)是怎樣的希望大家?guī)е@兩個(gè)問題閱讀下文。其中，前中后序，表示的是節(jié)點(diǎn)與它的左右子樹節(jié)點(diǎn)遍歷訪問的先后順序。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 想學(xué)好前端，先練好內(nèi)功，內(nèi)功不行，...
摘要：是棧，它繼承于。滿二叉樹除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子葉且葉子結(jié)點(diǎn)都處在最底層的二叉樹。沒有鍵值相等的節(jié)點(diǎn)。這是數(shù)據(jù)庫(kù)選用樹的最主要原因。 在我們學(xué)習(xí)Java的時(shí)候，很多人會(huì)面臨我不知道繼續(xù)學(xué)什么或者面試會(huì)問什么的尷尬情況（我本人之前就很迷茫）。所以，我決定通過這個(gè)開源平臺(tái)來幫助一些有需要的人，通過下面的內(nèi)容，你會(huì)掌握系統(tǒng)的Java學(xué)習(xí)以及面試的相關(guān)知識(shí)。本來是想通過Gitbook的...
摘要：原文博客地址學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)四樹知乎專欄簡(jiǎn)書專題前端進(jìn)擊者知乎前端進(jìn)擊者簡(jiǎn)書博主博客地址的個(gè)人博客人之所能，不能兼?zhèn)?，棄其所短，取其所長(zhǎng)。通常子樹被稱作左子樹和右子樹。敬請(qǐng)期待數(shù)據(jù)結(jié)構(gòu)篇最后一篇文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)五圖參考文章樹數(shù)據(jù)結(jié)構(gòu)二叉樹 前言 總括： 本文講解了數(shù)據(jù)結(jié)構(gòu)中的[樹]的概念，盡可能通俗易懂的解釋樹這種數(shù)據(jù)結(jié)構(gòu)的概念，使用javascript實(shí)現(xiàn)了樹，如有紕漏，歡迎批評(píng)指正。 ...
摘要：可以看到，一次左單旋將右側(cè)子樹的高度減小了，而左側(cè)子樹的高度增加了。如圖，對(duì)進(jìn)行右單旋，需要左子樹的右子樹的高度小于等于左子樹的高度，否則不能達(dá)到平衡的效果，只是把不平衡性從左邊轉(zhuǎn)移到了右邊。 AVL樹 普通二叉搜索樹可能出現(xiàn)一條分支有多層，而其他分支卻只有幾層的情況，如圖1所示，這會(huì)導(dǎo)致添加、移除和搜索樹具有性能問題。因此提出了自平衡二叉樹的概念，AVL樹（阿德爾森-維爾斯和蘭迪斯樹...
閱讀 3417·2021-11-25 09:43
閱讀 3471·2021-11-19 09:40
閱讀 2478·2021-10-14 09:48
閱讀 1295·2021-09-09 11:39
閱讀 1933·2019-08-30 15:54
閱讀 2829·2019-08-30 15:44
閱讀 2003·2019-08-29 13:12
閱讀 1550·2019-08-29 12:59
