<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Title</title>
</head>
<body>
<script>
// 二叉搜索树
let Node = function (value) {
this.value = value;
this.right = null;
this.left = null;
this.isFirst = false;
};
class BST {
constructor(value) {
let node = new Node(value);
this.root = node;
this.count = 0;
}
size() {
return this.count
}
isEmpty() {
return this.count === 0
}
insert(value) {
if (this.root === null) {
this.root = new Node(value);
this.count = 1;
} else {
this.root = this._insert(this.root, value);
this.count++
}
}
_insert(node, value) {
if (node === null) {
return new Node(value)
}
if (node.value === value) {
return;
} else if (value < node.value) {
node.left = this._insert(node.left, value)
} else {
node.right = this._insert(node.right, value)
}
return node;
}
contain(value) {
return this._contain(this.root, value)
}
_contain(node, value) {
if (node === null) return false
if (node.value === value) {
return true
} else if (node.left && node.value > value) {
return this._contain(node.left, value)
} else if (node.right && node.value < value) {
return this._contain(node.right, value)
}
}
search(value) {
return this._search(this.root, value)
}
_search(node, value) {
if (node === null) return null
if (node.value === value) {
return node.value
} else if (node.left && node.value > value) {
return this._search(node.left, value)
} else if (node.right && node.value < value) {
return this._search(node.right, value)
}
return null
}
preOrder(node) {
if (node !== null) {
console.log(node.value)
this.preOrder(node.left)
this.preOrder(node.right)
}
}
preOrderNR(node) {
if (!node) return;
let stack = [],
root;
stack.push(node);
while (stack.length) {
root = stack.pop();
if (root.right) stack.push(root.right);
if (root.left) stack.push(root.left);
console.log(root.value)
}
}
preOrderMorris(node) {
if (!node) return null;
let pre;
while (node) {
if (!node.left) {
console.log(node.value);
node = node.right;
} else {
pre = node.left;
while (pre.right && pre.right !== node) {
pre = pre.right;
}
if (!pre.right) {
console.log(node.value);
pre.right = node;
node = node.left
} else {
node = node.right;
pre.right = null;
}
}
}
}
inOrder(node) {
if (node !== null) {
this.inOrder(node.left);
console.log(node.value);
this.inOrder(node.right)
}
}
inOrderNR(node) {
if (!node) return
let stack = [],
root;
while (true) {
while (node) {
stack.push(node);
node = node.left
}
if (!stack.length) break;
root = stack.pop();
console.log(root.value);
root = root.right;
}
}
inOrderMorris(node) {
if (!node) return null;
let pre;
while (node) {
if (!node.left) {
console.log(node.value)
node = node.right
} else {
pre = node.left
while (pre.right && pre.right !== node) {
pre = pre.right
}
if (!pre.right) {
pre.right = node
node = node.left
} else {
console.log(node.value)
node = node.right
}
}
}
}
postOrder(node) {
if (node !== null) {
this.postOrder(node.left)
this.postOrder(node.right)
console.log(node.value)
}
}
postOrderNR(node) {
if (!node) return;
let stack = [],
currNode = node,
rightNode = null;
stack.push(currNode)
while (stack.length) {
while (currNode.left) {
stack.push(currNode.left)
currNode = currNode.left;
}
currNode = stack.pop()
while (!currNode.right || currNode.right === rightNode) {
console.log(currNode.value)
rightNode = currNode
currNode = stack.pop()
}
stack.push(currNode)
currNode = currNode.right
}
}
reverse(p1, p2) {
if (p1 === p2) return;
let x = p1,
y = p1.right,
temp;
while (true) {
temp = y.right;
y.right = x;
x = y;
y = temp;
if (x === p2) break;
}
}
printReverse(p1, p2) {
this.reverse(p1, p2);
let pNode = p2;
while (true) {
console.log(pNode.value);
if (pNode === p1) break;
pNode = pNode.right;
}
this.reverse(p2, p1);
}
postOrderMorris(node) {
if (!node) return;
let root = new Node(null),
pre;
root.left = node;
while (root) {
if (!root.left) {
root = root.right;
} else {
pre = root.left;
while (pre.right && pre.right !== root) {
pre = pre.right;
}
if (!pre.right) {
pre.right = root;
root = root.left;
} else {
this.printReverse(root.left, pre);
pre.right = null;
root = root.right
}
}
}
}
miniNum(node) {
if (!this.root) return;
while (node) {
if (!node.left) {
return node
}
node = node.left
}
}
removeMin(node) {
let pNode = node,
minNode = node.left,
rightNode = null;
while (minNode && minNode.left) {
pNode = pNode.left
minNode = minNode.left
}
if (minNode.right) {
rightNode = minNode.right
}
pNode.left = rightNode
return node;
}
maxNum(node) {
if (!this.root) return;
while (node) {
if (!node.right) {
return node;
}
node = node.right
}
}
removeMax(node) {
let pNode = node,
maxNode = node.right,
leftNode = null;
while (maxNode && maxNode.right) {
pNode = pNode.right
maxNode = maxNode.right
}
if (maxNode.left) {
leftNode = maxNode.left
}
pNode.right = leftNode
return node;
}
remove(node, e) {
this.root = this._remove(node, e);
this.count--;
}
_remove(node, e) {
if (!node) return null;
if (node.value > e.value) {
node.left = this._remove(node.left, e);
} else if (node.value < e.value) {
node.right = this._remove(node.right, e);
} else {
if (node.left === null) {
let rightNode = node.right;
node.right = null;
return rightNode;
} else if (node.right === null) {
let leftNode = node.left;
node.left = null;
return leftNode;
}
let successor = this.miniNum(node.right);
successor.right = this.removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
return successor;
}
}
levelOrder() {
let queue = [];
queue.push(this.root);
while (queue.length) {
let node = queue.shift();
console.log(node.value);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
}
</script>
</body>
</html>
网友评论