Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
206 lines (185 sloc) 3.96 KB
<!DOCTYPE html>
<html>
<head>
<title>Binary Tree</title>
</head>
<body>
<script type="text/javascript">
// 二叉树的节点结构
class Node {
constructor (key) {
this.key = key
this.left = null
this.right = null
}
}
// 二叉树
class BinaryTree {
// 根节点
constructor (root) {
this.root = root || null
}
// 插入一个节点
insert (key) {
let newNode = new Node(key)
if (this.root === null) {
this.root = newNode
} else {
this.insertNode(this.root, newNode)
}
}
// 在根节点下插入子节点
insertNode (node, newNode) {
if (node.key > newNode.key) {
if (node.left === null) {
node.left = newNode
} else {
this.insertNode(node.left, newNode)
}
} else {
if (node.right === null) {
node.right = newNode
} else {
this.insertNode(node.right, newNode)
}
}
}
_inOrderTraverseNode (node, callback) {
if (node !== null) {
this._inOrderTraverseNode(node.left, callback)
callback(node.key)
this._inOrderTraverseNode(node.right, callback)
}
}
// 中序遍历
inOrderTraverse (callback) {
this._inOrderTraverseNode(this.root, callback)
}
_preOrderTraverseNode (node, callback) {
if (node !== null) {
callback(node.key)
this._preOrderTraverseNode(node.left, callback)
this._preOrderTraverseNode(node.right, callback)
}
}
// 前序遍历
preOrderTraverse (callback) {
this._preOrderTraverseNode(this.root, callback)
}
_postOrderTraverseNode (node, callback) {
if (node !== null) {
this._postOrderTraverseNode(node.left, callback)
this._postOrderTraverseNode(node.right, callback)
callback(node.key)
}
}
// 后序遍历
postOrderTraverse (callback) {
this._postOrderTraverseNode(this.root, callback)
}
// 最小值
min () {
return this._minNode(this.root)
}
_minNode (node) {
if (node) {
while (node && node.left !== null) {
node = node.left
}
return node.key
}
return null
}
// 最大值
max () {
return this._maxNode(this.root)
}
_maxNode (node) {
if (node) {
while(node && node.right) {
node = node.right
}
return node.key
}
return null
}
// 查找
search (key) {
return this._searchNode(this.root, key)
}
_searchNode (node, key) {
if (node === null) {
return false
}
if (key < node.key) {
return this._searchNode(node.left, key)
} else if (key > node.key) {
return this._searchNode(node.right, key)
} else {
return true
}
}
// 删除节点
remove (key) {
this._removeNode(this.root, key)
}
findMinNode (node) {
if (node) {
while(node && node.left) {
node = node.left
}
return node
}
return null
}
_removeNode (node, key) {
if (node === null) {
return null
}
if (key < node.key) {
node.left = this._removeNode(node.left, key)
return node
} else if (key > node.key) {
node.right = this._removeNode(node.right, key)
return node
} else {
// 叶子节点情况直接删除
if (node.left === null && node.right === null) {
node = null
return node
}
// 有左或右子树的情况,直接将子树替换为删除的节点
if (node.left === null) {
node = node.right
return node
} else if (node.right === null) {
node = node.left
return node
}
// 同时有两个子树的情况,将右子树最小的节点替换到被删除的节点
let aux = this.findMinNode(node.right)
node.key = aux.key
node.right = this._removeNode(node.right, aux.key)
return node
}
}
}
const tree = new BinaryTree()
let arr = [8, 3, 10, 1, 6, 14, 4, 7, 13]
arr.forEach((key) => {
tree.insert(key)
})
console.log(tree)
function cb (key) {
console.log(key)
}
//
tree.postOrderTraverse(cb)
console.log('min: ', tree.min())
console.log('max: ', tree.max())
console.log('search 1:', tree.search(1))
tree.remove(8)
console.log(tree)
</script>
</body>
</html>
You can’t perform that action at this time.