```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())
```
