<!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>
2019-07-16 二叉搜索树
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 1. 树结构示意图 补充： 兄弟节点：具有相同父节点的节点互称为兄弟节点。 树的深度：从根节点开始（其深度为0）自...
- 2019 iOS面试题大全---全方面剖析面试2018 iOS面试题---算法相关1、七种常见的数组排序算法整理(...
- BST树即二叉搜索树：1.所有非叶子结点至多拥有两个儿子（Left和Right）；2.所有结点存储一个关键字；3....
- 关于树的总结从二叉树->二叉搜索树->平衡二叉树->红黑树->B树与B+树 B+树介绍 B树、B-树、B+树、B*...
