```js
// 排序二叉树
function BinaryTree () {
// 根节点
var root = null
// 节点类
var Node = function (key) {
this.key = key
this.left = null
this.right = null
}
// 获取二叉树所有节点
this.getNodes = function () {
return root
}
/**
* 二叉树节点插入
*/
var insertNode = function (node, newNode) {
if(newNode.key < node.key) {
if (!node.left) {
node.left = newNode
} else {
insertNode(node.left, newNode)
}
} else {
if (!node.right) {
node.right = newNode
} else {
insertNode(node.right, newNode)
}
}
}
// 插入节点
this.insert = function (key) {
var newNode = new Node(key)
if (!root) {
root = newNode
} else {
insertNode(root, newNode)
}
}
/**
* 二叉树遍历
*/
var inOrderTraverseNode = function (node, callback) {
if (node) {
inOrderTraverseNode(node.left, callback)
callback(node.key)
inOrderTraverseNode(node.right, callback)
}
}
var preOrderTraverseNode = function (node, callback) {
if (node) {
callback(node.key)
inOrderTraverseNode(node.left, callback)
inOrderTraverseNode(node.right, callback)
}
}
var postOrderTraverseNode = function (node, callback) {
if (node) {
postOrderTraverseNode(node.left, callback)
postOrderTraverseNode(node.right, callback)
callback(node.key)
}
}
// 中序遍历二叉树 (用与升序排序二叉树)
this.inOrderTraverse = function (callback) {
inOrderTraverseNode(root, callback)
}
// 前序遍历二叉树 (用于复制二叉树)
this.preOrderTraverse = function (callback) {
preOrderTraverseNode(root, callback)
}
// 后序遍历二叉树 (用于遍历文件系统的所有子文件夹)
this.postOrderTraverse = function (callback) {
postOrderTraverseNode(root, callback)
}
/**
* 二叉树查找
*/
// 查找二叉树中值最小的节点
this.min = function () {
var node = root
if (node) {
while (node && node.left) {
node = node.left
}
return node.key
}
return null
}
// 查找二叉树中值最大的节点
this.max = function () {
var node = root
if (node) {
while (node && node.right) {
node = node.right
}
return node.key
}
return null
}
// 查找指定节点
this.search = function (key) {
var node = root
while (node) {
if (key < node.key) {
node = node.left
} else if (key > node.key) {
node = node.right
} else {
return true
}
}
return false
}
/**
* 删除二叉树节点
*/
var findMinNode = function (node) {
if (node) {
while (node && node.left) {
node = node.left
}
return node
}
return null
}
var removeNode = function (node, key) {
if (!node) {
return null
}
if (key < node.key) {
node.left = removeNode(node.left, key)
} else if (key > node.key) {
node.right = removeNode(node.right, key)
} else {
// 找到要删除节点的位置
if (!node.left && !node.right) {
node = null
} else if (!node.left) {
node = node.right
} else if (!node.right) {
node = node.left
} else {
var aux = findMinNode(node.right)
node.key = aux.key
node.right = removeNode(node.right, aux.key)
}
}
return node
}
this.remove = function (key) {
root = removeNode(root, key)
}
}
var binaryTree = new BinaryTree()
var nodes = [8,3,10,1,6,14,4,7,13]
nodes.forEach(key => {
binaryTree.insert(key)
})
binaryTree.inOrderTraverse(key => console.log(key))
binaryTree.preOrderTraverse(key => console.log(key))
binaryTree.postOrderTraverse(key => console.log(key))
console.log(binaryTree.min())
console.log(binaryTree.max())
console.log(binaryTree.search(6))
console.log(binaryTree.search(5))
binaryTree.remove(3)
console.log(binaryTree.getNodes())
```
