树是一种有层次的数据结构，通常用于存储具有层次性的数据。比如上下级的关系图，动物的分类图等。树的类型分好几种，无序树、有序树和二叉树等等。但最常应用的还是二叉树，其特点为每个节点最多含有两个子树。
尝试手动构建一颗二叉树。
过程如下：
class BinaryTreeNode {
constructor(element) {
this.element = element
this.left = null
this.right = null
}
}
let n1 = new BinaryTreeNode(1)
let n2 = new BinaryTreeNode(2)
let n3 = new BinaryTreeNode(3)
n1.left = n2
n1.right = n3
console.log(n1)
// 输出二叉树结构：
// {
// element: 1,
// left: { element: 2, left: null, rgiht: null },
// right: { element: 3, left: null, rgiht: null },
// }
它或者是一棵空树，或者是具有下列性质的二叉树：
class BinarySearchTreeNode {
index: number
element: any
left: (null | BinarySearchTreeNode)
right: (null | BinarySearchTreeNode)
constructor(index: number, element: any) {
this.index = index
this.element = element
this.left = null
this.right = null
}
}
class BinarySearchTree {
length: number
root: (null | BinarySearchTreeNode)
constructor() {
this.length = 0
this.root = null
}
}
实现思路：根据二叉查找树的有序性能够让节点不断接近它合适的插入位置。
在此之前收集的两个条件如下：
index的值大小。接下来就需要利用上面这两个条件，将传入的index参数不断与树中已存在的节点的index进行大小比较。直到它在树中找到合适的位置，执行新节点的插入操作。
insert(index: number, element: any = null): BinarySearchTree {
if (this.root === null) {
this.root = new BinarySearchTreeNode(index, element)
} else {
let node: (null | BinarySearchTreeNode) = this.root
while (1) {
if (index === node!.index) {
throw new Error(`${index} already exists`)
} else if (index < node!.index) {
if (node!.left === null) {
node!.left = new BinarySearchTreeNode(index, element)
break
}
node = node!.left
} else if (index > node!.index) {
if (node!.right === null) {
node!.right = new BinarySearchTreeNode(index, element)
break
}
node = node!.right
}
}
}
this.length++
return this
}
实现思路：让待查找节点值在遍历过程中不断接近结果。
如果当前节点不为空，在未到达叶子节点之前仍需对这颗树进行遍历，直到找到值。
如果遍历已到达叶子节点，都没有找到值。说明值根本就不存在，我们直接终止遍历。
search(index: number): (void | boolean) {
if (this.isEmpty()) {
throw new Error('BinarySearchTree is empty')
} else {
let node: (null | BinarySearchTreeNode) = this.root
while (node !== null) {
if (index === node!.index) {
return true
} else if (index < node!.index) {
node = node!.left
} else if (index > node!.index) {
node = node!.right
}
}
if (!node) { return false }
}
}
删除的方法依然是在迭代的基础上，需要考虑四种不同节点情况，分别如下：
removeNode(node: (null | BinarySearchTreeNode)): (null | BinarySearchTreeNode) {
if (node!.right === null && node!.left === null) {
node = null
} else if (node!.right === null) {
node = node!.left
} else if (node!.left === null) {
node = node!.right
} else if (node!.right !== null && node!.left !== null) {
let temp: (null | BinarySearchTreeNode) = this.minNode(node!.right)
this.remove(temp!.index)
node!.index = temp!.index
node!.element = temp!.element
this.length++
}
return node
}
minNode方法：查找当前节点的右子树最小值
minNode(node: (null | BinarySearchTreeNode)): (null | BinarySearchTreeNode) {
while (node!.left !== null) {
node = node!.left
}
return node
}
remove方法：若index有效，遍历将会到达待删除节点的前一个节点，执行removeNode方法删除节点
remove(index: number): BinarySearchTree {
if (this.isEmpty()) {
throw new Error('BinarySearchTree is empty')
} else {
let node: (null | BinarySearchTreeNode) = this.root
while (node !== null) {
if (index === node!.index) {
this.root = this.removeNode(node)
break
} else if (node!.left !== null && index === node!.left.index) {
node!.left = this.removeNode(node!.left)
break
} else if (node!.right !== null && index === node!.right.index) {
node!.right = this.removeNode(node!.right)
break
} else if (index < node!.index) {
node = node!.left
} else if (index > node!.index) {
node = node!.right
}
}
if (!node) { throw new Error(`${index} does not exist`) }
this.length--
return this
}
}
注意：我们的需求是让二叉树查找树中待删除节点的前一个节点属性发生改变，让实例对象产生引用值的特点从而实现删除的效果。如果我们直接遍历到被删除节点，无论对这个节点（变量）作任何修改，都不会反映到实例对象上。来看下面的例子：
let a = { name: "小明", age: 20 }
let b = a // a和b指向同一地址
b.age = null // 此时产生效果，a.age也会变为null
b = null // b被重新赋值，a和b不会指向同一地址。所以a不会变为null
递归实现如下：
前序遍历（根左右）
export const preOrderTraversal = (tree: BinarySearchTree) => {
let result: Array<{ index: number, element: any }> = []
preOrderTraversalNode(tree!.root, result)
return result
}
const preOrderTraversalNode = (
node: (null | BinarySearchTreeNode),
result: Array<{ index: number, element: any }>) => {
if (node !== null) {
result.push({ index: node!.index, element: node!.element })
preOrderTraversalNode(node!.left, result)
preOrderTraversalNode(node!.right, result)
}
}
中序遍历（左根右）
export const inOrderTraversal = (tree: BinarySearchTree) => {
let result: Array<{ index: number, element: any }> = []
inOrderTraversalNode(tree!.root, result)
return result
}
const inOrderTraversalNode = (
node: (null | BinarySearchTreeNode),
result: Array<{ index: number, element: any }>) => {
if (node !== null) {
inOrderTraversalNode(node!.left, result)
result.push({ index: node!.index, element: node!.element })
inOrderTraversalNode(node!.right, result)
}
}
后序遍历（左右根）
export const postOrderTraversal = (tree: BinarySearchTree) => {
let result: Array<{ index: number, element: any }> = []
postOrderTraversalNode(tree!.root, result)
return result
}
const postOrderTraversalNode = (
node: (null | BinarySearchTreeNode),
result: Array<{ index: number, element: any }>) => {
if (node !== null) {
postOrderTraversalNode(node!.left, result)
postOrderTraversalNode(node!.right, result)
result.push({ index: node!.index, element: node!.element })
}
}
层序遍历（层级记录）
export const levelOrderTraversal = (tree: BinarySearchTree) => {
let result: Array<Array<{ index: number, element: any }>> = []
levelOrderTraversalNode(tree!.root, result, 0)
return result
}
const levelOrderTraversalNode = (
node: (null | BinarySearchTreeNode),
result: Array<Array<{ index: number, element: any }>>, level: number) => {
if (!result[level]) { result[level] = [] }
result[level].push({ index: node!.index, element: node!.element })
if (node!.left) { levelOrderTraversalNode(node!.left, result, level + 1) }
if (node!.right) { levelOrderTraversalNode(node!.right, result, level + 1) }
}
迭代实现如下：
前序遍历（根左右）
const preOrderTraversal = (tree: BinarySearchTree) => {
let stack: Stack = new Stack()
let node: (null | BinarySearchTreeNode) = tree!.root
let result: Array<{ index: number, element: any }> = []
while (node !== null || !stack.isEmpty()) {
while (node !== null) {
stack.push(node)
result.push({ index: node!.index, element: node!.element })
node = node!.left
}
node = stack.pop()
node = node!.right
}
return result
}
中序遍历（左根右）
const inOrderTraversal = (tree: BinarySearchTree) => {
let stack: Stack = new Stack()
let node: (null | BinarySearchTreeNode) = tree!.root
let result: Array<{ index: number, element: any }> = []
while (node !== null || !stack.isEmpty()) {
while (node !== null) {
stack.push(node)
node = node!.left
}
node = stack.pop()
result.push({ index: node!.index, element: node!.element })
node = node!.right
}
return result
}
后序遍历（左右根）
export const postOrderTraversal = (tree: BinarySearchTree) => {
let stack: Stack = new Stack()
let node: (null | BinarySearchTreeNode) = tree!.root
let result: Array<{ index: number, element: any }> = []
let prev: (null | BinarySearchTreeNode) = null
while (node !== null || !stack.isEmpty()) {
while (node !== null) {
stack.push(node)
node = node!.left
}
node = stack.pop()
if (node!.right === null || node!.right === prev) {
result.push({ index: node!.index, element: node!.element })
prev = node
node = null
} else {
stack.push(node)
node = node!.right
}
}
return result
}
层序遍历（广度优先搜索）
const levelOrderTraversal = (tree: BinarySearchTree) => {
let result: Array<Array<{ index: number, element: any }>> = []
if (!(tree!.root)) { return result }
let queue: Queue = new Queue()
let node: (null | BinarySearchTreeNode) = tree!.root
queue.enqueue(node)
while (!queue.isEmpty()) {
result.push([])
const { length } = queue
for (let i = 0; i < length; i++) {
node = queue.dequeue()
result[result.length - 1].push({ index: node!.index, element: node!.element })
if (node!.left) { queue.enqueue(node!.left) }
if (node!.right) { queue.enqueue(node!.right) }
}
}
return result
}
至此已完成二叉查找树的增删查和遍历方法，迭代实现的优势在于JavaScript每调用一个函数就会产生一个执行上下文将其推入函数调用栈中。如果我们构建的二叉查找树十分的高，递归就有可能出现爆栈问题。
本文相关代码已放置我的Github仓库
