RubyLouvre
commented
6 years ago Open RubyLouvre opened 6 years ago
RubyLouvre
commented
6 years ago RubyLouvre
commented
6 years ago 二叉树的插入
insert(data) {
var dir = this._insertLeft = !this._insertLeft;
function insertIt(node, data) {
if (node.data === data) {
return false;
} else if (!node.left) {
node.left = new Node(data);
node.left.parent = node;
return true;
} else if (!node.right) {
node.right = new Node(data);
node.right.parent = node;
return true;
} else {
if (dir === true) {
return insertIt(node.left, data);//递归
} else {
return insertIt(node.right, data);//递归
}
}
}
var ret = false;
if (!this.root) {
this.root = new Node(data);
ret = true;
} else {
ret = insertIt(this.root, data);
}
if (ret) {
this._size++
}
return ret;
}二叉树的删除
remove(data) {
var p = this.find(data);
if (p) {
this.removeNode(p);//方便递归
this._size--;
}
}
removeNode(node) {
//replace表示删除之后顶替上来的结点
//parent为replace结点的父结点
// 如果删除的结点左右孩子都有
if (node.left != null && node.right != null) {
var succ = null;
for (succ = node.right; succ.left != null; succ = succ.left); //找到后继
node.data = succ.data; //覆盖值
this.removeNode(succ); //递归删除，只可能递归一次
} else {
// 叶子或只有一个孩子的情况
var child = node.left || node.right || null
this.transplant(node, child);
}
}前驱与后缀
function precursor(node){
var ret;
if(node.left){//如果有左子树
var ret = node.left
while(ret.right){//在左子树查找最大的右结点
ret = ret.right
}
return ret;
}else{
var p = node.parent;
while(p && p.left === node){
node = p;//找到一个父节点，是其父节点的父节点的左孩子
p = p.parent;
}
return p;
}
}
function successor(node){
if(node.right){//如果有右子树
var ret = node.left
while(ret.left){//在右子树查找最大的左结点
ret = ret.left
}
return ret;
}else{
var p = node.parent;
while(p && p.right === node){
node = p;//找到一个父节点，是其父节点的父节点的右孩子
p = p.parent;
}
return p;
}
}打印每一层的节点
printNodeByLevel(callback) {
var queue = []
var out = []
var node = this.root;
if (node) {
queue.push(node)
queue.push(0)
}
while (queue.length) {
node = queue.shift()//先进先出
if (node) {
callback(node)
if (node.left) {
queue.push(node.left)
}
if (node.right) {
queue.push(node.right)
}
} else if(queue.length){
queue.push(0)
console.log("=======")
}
}
}
//-----------
var tree = new SBT(); //10, 50, 40, 30, 20, 60, 55, 54, 53, 52, 51, 56
[10, 50, 47, 30, 200, 60, 55, 504, 53, 52, 51, 56].forEach(function (el, i) {
tree.insert(el)
})
var array = []
tree.printNodeByLevel(function(node){
if(node !== 0){
array.push(node.data)
}else{
console.log(array.join(","))
array.length = 0
}
})
console.log(array.join(","))
array.length = 0
RubyLouvre
commented
6 years ago 水平打印
class Node {
constructor(data) {
this.data = data;
this.size = 1
this.left = null;
this.right = null;
this.parent = null;
}
update() {
var leftSize = this.left ? this.left.size : 0
var rightSize = this.right ? this.right.size : 0
this.size = leftSize + rightSize + 1;
}
};
class SBT {
constructor() {
this.root = null;
this._size = 0;
}
transplant(child, parent) {
if (!parent) {
this.root = child;
} else {
if (parent.data > child.data) {
parent.left = child
} else {
parent.right = child
}
}
if (child) {
child.parent = parent;
}
}
leftRotate(node) {
if (!node.right) {
return;
}
var child = node.right;
node.right = child.left;
if (child.left) {
//过继孩子
child.left.parent = node; //父属性修正1
}
this.transplant(child, node.parent) //父属性修正2
node.parent = child; //父属性修正3
child.left = node; //旋转
//其他属性更新
child.size = node.size;//child.update(),但直接赋值更快
node.update();
}
rightRotate(node) {
if (!node.left) {
return;
}
var child = node.left;
node.left = child.right;
if (child.right) {
//过继孩子
child.right.parent = node; //父属性修正1
}
this.transplant(child, node.parent) //父属性修正2
node.parent = child; //父属性修正3
child.right = node; //旋转
//其他属性更新
child.size = node.size;//child.update(),但直接赋值更快
node.update();
}
maintain(node, rightDeeper) {
var left = node.left;
var right = node.right;
if (!rightDeeper) {
if (!left) {
return
}
var rightSize = right && right.size || 0
var llSize = left.left && left.left.size || 0
var lrSize = left.right && left.right.size || 0
if (llSize > rightSize) {
this.rightRotate(node);
} else if (lrSize > rightSize) {
this.leftRotate(left);
this.rightRotate(node);
} else {
return;
}
} else {
if (!right) {
return
}
var leftSize = left && left.size || 0
var rrSize = right.right && right.right.size || 0
var rlSize = right.left && right.left.size || 0
if (rrSize > leftSize) {
this.leftRotate(node);
} else if (rlSize > leftSize) {
this.rightRotate(right);
this.leftRotate(node);
} else {
return;
}
}
}
size() {
return this.root ? this.root.size : 0
}
find(data) {
var node = this.root;
while (node) {
var diff = data - node.data
if (diff == 0) {
break
} else if (diff < 0) {
node = node.left;
} else {
node = node.right;
}
}
if (node) {
return node
}
return null
}
insert(data) {
if (!this.root) {
this.root = new Node(data);
this._size++;
return true;
}
var node = this.root,
parent, paths = [];
while (node) {
paths.push(node);
var diff = data - node.data;
parent = node;
if (diff == 0) {
return false;
} else if (diff < 0) {
node = node.left;
} else {
node = node.right;
}
}
var node = new Node(data);
node.parent = parent
this._size++;
if (diff < 0) {
parent.left = node;
} else {
parent.right = node;
}
for (var i = paths.length - 1; i >= 0; i--) {
parent = paths[i];
parent.size++;
this.maintain(parent, data >= parent.data);
}
return true;
}
remove(data) {
if (!this.root) {
return false
}
var node = this.find(data);
if (node) {
//两个孩子的情况
if (node.left && node.right) {
var succ = this.maxNode(node.left); //求后继
node.data = succ.data;
node = succ; //转为一个孩子的情况
}
//一个或零个孩子的情况
this._size--;
var child = node.left || node.right || null;
var parent = node.parent,
p = parent,
paths = []
while (p) {
paths.push(p)
p = p.parent;
}
if (parent.left == node) {
parent.left = child
} else {
parent.right = child
}
if (child) {
child.parent = parent; //parent的size发生变化
}
while (p = paths.shift()) {
p.size--;
this.maintain(p, data >= p.data);
}
}
}
maxNode(node) {
var node = node || this.root;
while (node.right) {
node = node.right
}
return node;
}
preOrder(callback) {//中左右
var stack = []
var node = this.root;
while (node != null || stack.length) {//将所有孩子压栈
if (node != null) {
callback(node);//先于left之前访问
stack.push(node);
node = node.left
} else {
node = stack.pop();
node = node.right
}
}
}
inOrder(callback) {//左中右
var stack = []
var node = this.root;
while (node != null || stack.length) {//将所有孩子压栈
if (node != null) {
stack.push(node);
node = node.left
} else {
node = stack.pop();
callback(node);//先于right前访问
node = node.right
}
}
}
postOrder(callback) {//左右中
var stack = []
var out = []
var node = this.root;
while (node || stack.length) {//将所有孩子压栈
if (node) {
stack.push(node);
out.push(node);
node = node.right;//先放右孩子
} else {
node = stack.pop();
node = node.left//先放左孩子
}
}
while (out.length) {
callback(out.pop())
}
}
height() {
return this.getNodeHeight(this.root);
}
printNodeByLevel(callback) {
var queue = []
var out = []
var node = this.root;
if (node) {
queue.push(node)
queue.push(0)
}
while (queue.length) {
node = queue.shift()//先进先出
if (node) {
callback(node)
if (node.left) {
queue.push(node.left)
}
if (node.right) {
queue.push(node.right)
}
} else if (queue.length) {
queue.push(0)
callback(0)
}
}
}
//获取指定结点的度
getNodeHeight(node) {
if (node === null) {//递归出口
return 0;
}
var leftChildHeight = this.getNodeHeight(node.left);
var rightChildHeight = this.getNodeHeight(node.right);
var max = Math.max(leftChildHeight, rightChildHeight);
return max + 1; //加上自己本身
}
breadthFirstTraval(callback) {
var queue = []
var out = []
var node = this.root;
node && queue.push(node)
while (queue.length) {
node = queue.shift()//先进先出
callback(node)
if (node.left) {
queue.push(node.left)
}
if (node.right) {
queue.push(node.right)
}
}
}
printNodeByLevel(callback) {
var queue = []
var out = []
var node = this.root;
if (node) {
queue.push(node)
queue.push(0)
}
while (queue.length) {
node = queue.shift()//先进先出
if (node) {
callback(node)
if (node.left) {
queue.push(node.left)
}
if (node.right) {
queue.push(node.right)
}
} else if (queue.length) {
callback(0)
queue.push(0) //用于分隔当前层
}
}
}
toString() {
//辅助方法，让数据居中对齐
const brickLen = 6, SW = " ", LINE = "_"
function displayData(node) {
var s = "(" + node.data + ")", right = true, isLeaf = !node.left && !node.right
for (var i = s.length; i < brickLen; i++) {
if (right) {
s = s + (isLeaf ? SW : LINE);
} else {
s = (isLeaf ? SW : LINE) + s;
}
right = !right
}
return s;
}
//创建4个字符的空白或下划线
function createPadding(s, n) {
var ret = "";
n = n || brickLen;
for (var i = 0; i < n; i++) {
ret += s;
}
return ret;
}
//====================================
//添加索引值
var index = 0;
tree.inOrder(function (el) {
el.index = index++;
})
// 收集每一层的结点
var allLevelNodes = [];
var array = [];
tree.printNodeByLevel(function (node) {
if (node !== 0) {
array.push(node);
} else {
allLevelNodes.push(array);
array = [];
}
})
if (array.length) {
allLevelNodes.push(array);
}
//brickes中有数据的层，branches只是用来放斜线的层,都是二维数组
var brickes = [];
var branches = [];
for (var i = 0, n = allLevelNodes.length; i < n; i++) {
if (!brickes[i]) {
brickes[i] = [];
branches[i] = [];
}
var cbrick = brickes[i];
var cbranch = branches[i];
var level = allLevelNodes[i];
while (level.length) {
var el = level.shift();
var j = el.index;
//确保cbrick[j]与cbranch[j]等长
cbrick[j] = displayData(el);
cbranch[j] = createPadding(SW, cbrick[j].length);
if (el.parent) {
var pbrick = brickes[i - 1];
var pbranch = branches[i - 1];
var pindex = el.parent.index;
if (el == el.parent.left) {//左子树
for (var k = j + 1; k < pindex; k++) {
pbrick[k] = createPadding(LINE);
}
for (var k = j + 1; k < pindex; k++) {
pbranch[k] = createPadding(SW);
}
pbranch[j] = createPadding(SW, brickLen - 1) + "/"
} else {//右子树
for (var k = pindex + 1; k < j; k++) {
pbrick[k] = createPadding(LINE);
}
for (var k = pindex + 1; k < j; k++) {
pbranch[k] = createPadding(SW);
}
pbranch[j] = "\\" + createPadding(SW, brickLen - 1)
}
}
j--;
inner:
while (j > -1) { //添加空白
if (cbrick[j] == null) {//将非空节点变成空字符串
cbrick[j] = createPadding(SW);
cbranch[j] = createPadding(SW)
} else {
break inner;
}
j--;
}
}
}
return brickes.map(function (el, i) {
return el.join("") + "\n" + branches[i].join("")
}).join("\n")
}
}
var tree = new SBT(); //10, 50, 40, 30, 20, 60, 55, 54, 53, 52, 51, 56
[10, 50, 47, 30, 200, 60, 55, 504, 53, 52, 51, 56].forEach(function (el, i) {
tree.insert(el)
})
console.log(tree + "")