树

TIP

树(Tree)是生活中树的一种抽象，模型中树为生活中树的旋转 180°，有一个根，连着根的是树干，树干发叉，形成树枝，树枝继续分化为更小的树枝，树枝最后形成叶子

结构

• 由 n（n ≥ 0）个节点构成的有限集合
• 当 n = 0 时，称为空树
• 当 n > 0 为非空树，它具备以下性质：
  1. 树中有一个称为根(Root)的特殊节点，用 r 表示
  2. 其余节点可分为 m(m > 0)个互不相交的有限集合 T1，T2，...，Tm，其中每个集合本身又是一棵树，称为原来树的子树(SubTree)

术语

1. 节点的度(Degree)：节点的子树个数，比如节点 B 的度为 2
2. 树的度：树的所有节点中最大的度数，如上图树的度为 2
3. 叶节点(Leaf)：度为 0 的节点（也称为叶子节点），如上图的 H、E、I、J、G 等；
4. 父节点(Parent)：度不为 0 的节点称为父节点，如上图节点 B 是节点 D 和 E 的父节点
5. 子节点(Child)：若 B 是 D 的父节点，那么 D 就是 B 的子节点
6. 兄弟节点(Sibling)：具有同一父节点的各节点彼此是兄弟节点，比如上图的 B 和 C，D 和 E 互为兄弟节点
7. 路径和路径长度：路径指的是一个节点到另一节点的通道，路径所包含边的个数称为路径长度，比如 A->H 的路径长度为 3
8. 节点的层次(Level)：规定根节点在 1 层，其他任一节点的层数是其父节点的层数加 1。如 B 和 C 节点的层次为 2
9. 树的深度(Depth)：树种所有节点中的最大层次是这棵树的深度，如上图树的深度为 4

三种表示方法

普通表示法

• 如图，树结构的组成方式类似于链表，都是由一个个节点连接构成。不过，根据每个父节点子节点数量的不同，每一个父节点需要的引用数量也不同
• 比如节点 A 需要 3 个引用，分别指向子节点 B，C，D；B 节点需要 2 个引用，分别指向子节点 E 和 F；K 节点由于没有子节点，所以不需要引用
• 这种方法缺点在于我们无法确定某一结点的引用数

儿子-兄弟表示法

• 这种表示方法可以完整地记录每个节点的数据
• 优点在于每一个节点中引用的数量都是确定的
• 每个节点记录三个数据：data 数据、leftChild 左子节点、rightSibling 右边第一个兄弟节点

儿子-兄弟旋转表示法

• 儿子-兄弟表示的树图经过顺时针旋转 45° 之后得到一颗二叉树
• 任何树都可以通过二叉树进行模拟
• 父子节点是通过引用连结，可以方便快速查找

二叉树

TIP

如果树中的每一个节点最多只能由两个子节点，这样的树就称为二叉树，程序中几乎所有的树都可以表示为二叉树

组成

• 二叉树可以为空，也就是没有节点
• 若二叉树不为空，则它由根节点和称为其左子树 TL 和右子树 TR 的两个不相交的二叉树组成

五种形态

特性

• 一个二叉树的第 i 层的最大节点树为：2^(i-1)，i >= 1
• 深度为 k 的二叉树的最大节点总数为：2^k - 1 ，k >= 1
• 对任何非空二叉树，若 n0 表示叶子节点的个数，n2 表示度为 2 的非叶子节点个数，那么两者满足关系：n0 = n2 + 1
• 如下图所示：H，E，I，J，G 为叶子节点，总数为 5；A，B，C，F 为度为 2 的非叶子节点，总数为 4；满足 n0 = n2 + 1 的规律

完美二叉树

• 完美二叉树(Perfect Binary Tree)也成为满二叉树(Full Binary Tree)，是一种特殊的二叉树
• 在二叉树中，除了最下一层的叶子节点外，每层节点都有 2 个子节点，这就构成了完美二叉树，即满二叉树

完全二叉树

• 完全二叉树(Complete Binary Tree)，是一种特殊的二叉树
• 完全二叉树必须满足以下条件：
  1. 除了二叉树最后一层外，其他各层的节点数都达到了最大值
  2. 最后一层的叶子节点从左向右是连续存在，只缺失右侧若干叶子节点
  3. 完美二叉树是特殊的完全二叉树
• 下图由于 D 缺失了右子节点，而 E 就有了 J、K 左右节点，所以它不是完全二叉树

数据存储

常见的二叉树存储方式为数组和链表：

(1) 数组存储

• 完全二叉树：按从上到下，从左到右的方式存储数据。左子节点的序号等于父节点序号 * 2，右子节点的序号等于父节点序号 * 2 + 1

节点	A	B	C	D	E	F	G	H	I
序号	1	2	3	4	5	6	7	8	9

• 非完全二叉树：需要转换成完全二叉树才能按照上面的方案存储，这样会浪费很大的存储空间

节点	A	B	C	^	^	F	^	^	^	^	^	^	M
序号	1	2	3	4	5	6	7	8	9	10	11	12	13

(2) 链表存储

• 完全二叉树和非安全二叉树都能存储，结构也一样的
• 每一个节点封装成一个 Node，Node 中包含存储的数据、左节点的引用和右节点的引用

二叉搜索树

TIP

二叉搜索树(BST，Binary Search Tree)，也称为二叉排序树和二叉查找树

性质

• 二叉搜索树是一棵二叉树，可以为空
• 如果不为空，则满足以下性质
  1. 非空左子树的所有键值小于其根节点的键值。比如图三中节点 6 的所有非空左子树的键值都小于 6
  2. 非空右子树的所有键值大于其根节点的键值；比如图三中节点 6 的所有非空右子树的键值都大于 6
  3. 左、右子树本身也都是二叉搜索树

• 如上图所示，图二和图三符合 3 个条件属于二叉树，图一不满足条件 3 所以不是二叉树
• 总结：二叉搜索树的特点主要是较小的值总是保存在左节点上，相对较大的值总是保存在右节点上
• 这种特点使得二叉搜索树的查询效率非常高，这也就是二叉搜索树中"搜索"的来源

搜索举例

上图为一个二叉搜索树，若想在其中查找数据 10，只需要查找 4 次，查找效率非常高

• 第 1 次：将 10 与根节点 9 进行比较，由于 10 > 9，所以 10 下一步与根节点 9 的右子节点 13 比较
• 第 2 次：由于 10 < 13，所以 10 下一步与父节点 13 的左子节点 11 比较
• 第 3 次：由于 10 < 11，所以 10 下一步与父节点 11 的左子节点 10 比较
• 第 4 次：由于 10 = 10，最终查找到数据 10

图解搜索过程如下：

总结：同样是 15 个数据，在排序好的数组中查询数据 10，如果是线性查找需要查询 10 次，如果是二分查找可以提高效率，二分查找如果用树表示出来的话就是一颗二叉搜索树，所以二叉搜索树的效率非常高

遍历方式

• 先序遍历
• 中序遍历
• 后序遍历
• 层序遍历

常见操作

• insert（key）：向树中插入一个新的键
• search（key）：在树中查找一个键，如果节点存在，则返回 true；如果不存在，则返回 false
• inOrderTraversal：通过中序遍历方式遍历所有节点
• preOrderTraversal：通过先序遍历方式遍历所有节点
• postOrderTraversal：通过后序遍历方式遍历所有节点
• min：返回树中最小的值/键
• max：返回树中最大的值/键
• remove（key）：从树中移除某个键

基本属性代码封装

图例说明

如上图所示：二叉搜索树有四个最基本的属性：指向节点的根(root)，节点中的键(key)、左指针(left)、右指针(right)

基础代码

// 创建二叉搜索树的类：BinarySearchTree
function BinarySerachTree() {
	// 节点内部类：创建节点构造函数
	function Node(key) {
		this.key = key
		this.left = null
		this.right = null
	}

	// 保存根的属性
	this.root = null
}

insert 插入

实现思路

• 首先，根据传入的 key 创建节点对象
• 然后，判断根节点是否存在，不存在时，直接把新节点作为二叉搜索树的根节点
• 最后，若存在根节点则调用内部方法 insertNode()用于查找插入点

// 1. insert方法：插入数据，对外给用户调用的方法
BinarySerachTree.prototype.insert = function (key) {
	// 1.1 根据key创建节点
	var newNode = new Node(key)
	// 1.2 判断根节点是否有值
	if (this.root == null) {
		// 根节点不存在，新节点作为根节点
		this.root = newNode
	} else {
		// 根节点存在，则调用内部的查找并插入节点方法
		this.insertNode(this.root, newNode)
	}
}

内部方法 insertNode()的实现思路:

• 根据比较传入的两个节点，一直查找新节点适合插入的位置，直到成功插入新节点为止
• 分类一：当 newNode.key < node.key 向左查找
  1. 情况 1：当 node 无左子节点时，直接插入
  2. 情况 2：当 node 有左子节点时，递归调用 insertNode()，直到遇到无左子节点，则成功插入 newNode 后，递归停止
• 分类二：当 newNode.key >= node.key 向右查找
  1. 情况 1：当 node 无右子节点时，直接插入
  2. 情况 2：当 node 有右子节点时，递归调用 insertNode()，直到遇到无右子节点，则成功插入 newNode 后，递归停止

// 内部用于递归插入节点的方法：用于比较节点从左边插入还是右边插入
BinarySerachTree.prototype.insertNode = function (node, newNode) {
	if (newNode.key < node.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)
		}
	}
}

测试

// 测试代码
var bst = new BinarySerachTree()

// 1. 测试insert方法：插入数据
bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(3)
bst.insert(9)
bst.insert(8)
bst.insert(10)
bst.insert(13)
bst.insert(12)
bst.insert(14)
bst.insert(20)
bst.insert(18)
bst.insert(25)

结果树如下：

如果这个时候, 我新插入一个数据 6, 那么插入的位置和顺序应该怎样的呢?

bst.insert(6)

新的结果树如下：

preOrderTraversal 先序遍历

遍历过程

• 首先，遍历根节点
• 然后，遍历其左子树
• 最后，遍历其右子树

代码实现

// 2. preOrderTraversal 方法：先序遍历
BinarySerachTree.prototype.preOrderTraversal = function (handler) {
	this.preOrderTraversalNode(this.root, handler)
}
// 封装内部方法，对某个节点进行遍历
BinarySerachTree.prototype.preOrderTraversalNode = function (node, handler) {
	if (node != null) {
		// 2.1 处理经过的节点
		handler(node.key)

		// 2.2 递归遍历经过节点的左子树的节点
		this.preOrderTraversalNode(node.left, handler)

		// 2.3 遍历经过节点的右子树的节点
		this.preOrderTraversalNode(node.right, handler)
	}
}

代码解析

• 首先，从根节点开始，优先查找节点
• 然后，遍历节点的左子树
• 最后，遍历节点的右子树

图解遍历

测试结果

// 2. 测试前序遍历结果
var resultString = ""
bst.preOrderTraversal(function (key) {
	resultString += key + " "
})
console.log(resultString) // 11 7 5 3 6 9 8 10 15 13 12 14 20 18 25

inOrderTraversal 中序遍历

遍历过程

• 首先，遍历其左子树
• 然后，遍历根(父)节点
• 最后，遍历其右子树

代码实现

// 3. inOrderTraversal 方法：中序遍历
BinarySerachTree.prototype.inOrderTraversal = function (handler) {
	this.inOrderTraversalNode(this.root, handler)
}
// 封装内部方法，对某个节点进行遍历
BinarySerachTree.prototype.inOrderTraversalNode = function (node, handler) {
	if (node != null) {
		// 3.1 递归遍历经过节点的左子树的节点
		this.inOrderTraversalNode(node.left, handler)

		// 3.2 处理经过的节点
		handler(node.key)

		// 3.3 遍历经过节点的右子树的节点
		this.inOrderTraversalNode(node.right, handler)
	}
}

代码解析

• 首先，从根节点找到最左节点，从最左节点开始，优先处理左子树，依次查找
• 然后，处理根(父)节点
• 最后，遍历节点的右子树

图解遍历

测试结果

// 3. 测试中序遍历结果
resultString = ""
bst.inOrderTraversal(function (key) {
	resultString += key + " "
})
console.log(resultString) // 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25

postOrderTraversal 后序遍历

遍历过程

• 首先，遍历其左子树
• 然后，遍历其右子树
• 最后，遍历根(父)节点

代码实现

// 4. postOrderTraversal 方法：后序遍历
BinarySerachTree.prototype.postOrderTraversal = function (handler) {
	this.postOrderTraversalNode(this.root, handler)
}
// 封装内部方法，对某个节点进行遍历
BinarySerachTree.prototype.postOrderTraversalNode = function (node, handler) {
	if (node != null) {
		// 4.1 递归遍历经过节点的左子树的节点
		this.postOrderTraversalNode(node.left, handler)

		// 4.2 遍历经过节点的右子树的节点
		this.postOrderTraversalNode(node.right, handler)

		// 4.3 处理经过的节点
		handler(node.key)
	}
}

代码解析

• 首先，从根节点找到最左节点，从最左节点开始，优先处理左子树，依次查找
• 然后，遍历节点的右子树
• 最后，处理根(父)节点

图解遍历

测试结果

// 4. 测试后续遍历结果
resultString = ""
bst.postOrderTraversal(function (key) {
	resultString += key + " "
})
console.log(resultString) // 3 6 5 8 10 9 7 12 14 13 18 25 20 15 11

min | max 最小值|最大值

• 最小值在二叉搜索树的最左边，代码只需要依次向左查找即可
• 最大值在二叉搜索树的最右边，代码只需要依次向右查找即可

代码实现

// 5. min 方法：获取最小值
BinarySerachTree.prototype.min = function () {
	// 5.1 获取根节点
	let node = this.root
	// 5.2 依次向左不断查找，直到左子节点为null
	while (node.left != null) {
		node = node.left
	}
	// 5.3 返回key值
	return node.key
}

// 6. max 方法：获取最大值
BinarySerachTree.prototype.max = function () {
	// 6.1 获取根节点
	let node = this.root
	// 6.2 依次向右不断查找，直到右子节点为null
	while (node.right != null) {
		node = node.right
	}
	// 6.3 返回key值
	return node.key
}

图解遍历

测试结果

// 5. 获取最小值
console.log(bst.min()) // 3
// 6. 获取最大值
console.log(bst.max()) // 25

search 搜索

• 从根节点开始将需要查找节点的 key 值与之比较
• 若 node.key < root 则向左查找
• 若 node.key > root 就向右查找，直到找到或查找到 null 为止
• 既可以使用递归，也可以使用循环

代码实现

// 7. search 方法： 搜索特定的值
// 方式一：循环查找
BinarySerachTree.prototype.search = function (key) {
	// 7.1 获取根节点
	let node = this.root

	// 7.2 循环搜索key
	while (node != null) {
		if (key < node.key) {
			// 小于根(父)节点就往左边找
			node = node.left
		} else if (key > node.key) {
			// 大于根(父)节点就往右边找
			node = node.right
		} else {
			// 找到就返回true
			return true
		}
	}
	// 7.3 全部没找到就返回false
	return false
}

// 方式二：递归找到
BinarySerachTree.prototype.search = function (key) {
	return this.searchNode(this.root, key)
}
BinarySerachTree.prototype.searchNode = function (node, key) {
	// 1.如果传入的node为null那么, 那么就退出递归
	if (node === null) {
		return false
	}

	// 2.判断node节点的值和传入的key大小
	if (node.key > key) {
		// 2.1.传入的key较小, 向左边继续查找
		return this.searchNode(node.left, key)
	} else if (node.key < key) {
		// 2.2.传入的key较大, 向右边继续查找
		return this.searchNode(node.right, key)
	} else {
		// 2.3.相同, 说明找到了key
		return true
	}
}

测试结果

// 7. 查找特定的值
console.log(bst.search(10)) // true
console.log(bst.search(21)) // false

remove 删除

实现思路

• 第一步：先找到需要删除的节点，若没找到，则不需要删除
• 第二步：找到需要删除的节点后，又分为以下 3 类
  1. 该节点是叶子节点
  2. 该节点不是叶子节点，有一个子节点
  3. 该节点不是叶子节点，有两个子节点

第一步：先找到需要删除的节点，若没找到，则不需要删除

// 8. remove 方法：删除节点
BinarySearchTree.prototype.remove = function (key) {
	/* 8.1 寻找需要删除的节点*/
	// 8.1.1 定义临时保存的变量
	let current = this.root // current保存删除的节点
	let parent = null // parent保存current的父节点
	let isLeftChild = true // isLeftChild保存current是否为parent的左节点

	// 8.1.2 开始查找需要删除的节点
	while (current.key != key) {
		parent = current

		// 判断向左还是向右查找
		if (key < current.key) {
			// 小于往左查找
			isLeftChild = true
			current = current.left
		} else {
			// 大于往后查找
			isLeftChild = false
			current = current.right
		}

		// 找到最后依然没有找到相等的节点
		if (current == null) {
			return false
		}
	}
	//结束while循环后：current.key = key
	return true
}

第二步：找到需要删除的节点后，后分 3 种情况

• 分类一：该节点是叶子节点，没有子节点
  1. 当该叶子节点时根节点时，即只有一个单独的根节点，直接删除
  2. 当该叶子节点不是根节点时，就将对应父节点的 left 或 right 设值为 null

// 分类1：删除的是叶子节点(没有子节点)
if (current.left == null || current.right == null) {
	// 判断节点类型
	if (current == this.root) {
		// 如果是根节点，直接置null
		this.root = null
	} else if (isLeftChild) {
		// 只有左子节点
		parent.left = null
	} else {
		// 只有右子节点
		parent.right = null
	}
}

• 分类二：该节点不是叶子节点，有一个子节点

当 current 只有左子节点时(current.right == null):

当 current 只有右子节点时(current.left == null):

// 分类2：删除的是只有一个节点
if (current.right == null) {
	// 分类2：删除的节点有一个子节点：当current存在左子节点时
	if (current == this.root) {
		// 如果是根节点
		this.root = current.left
	} else if (isLeftChild) {
		// 只有左子节点
		parent.left = current.left
	} else {
		// 只有右子节点
		parent.right = current.left
	}
} else if (current.left == null) {
	// 分类2：删除的节点有一个子节点：当current存在右子节点时
	if (current == this.root) {
		// 如果是根节点
		this.root = current.right
	} else if (isLeftChild) {
		// 只有左子节点
		parent.left = current.right
	} else {
		// 只有右子节点
		parent.right = current.right
	}
}

• 分类三：该节点不是叶子节点，有两个子节点

需要找到替代当前节点的子节点：前驱 或 后继

• 在二叉搜索树中，current 左子树中比 current 小一点点的节点，即 current 左子树中的最大值，称为 current 节点的前驱。比如下图中的节点 5 就是节点 7 的前驱
• 在二叉搜索树中，current 左子树中比 current 大一点点的节点，即 current 右子树中的最小值，称为 current 节点的后继。比如下图中的节点 8 就是节点 7 的后继

代码实现思路

• 查找需要被删除的节点 current 的后继时，则需要在 current 的右子树中查找最小值，即在 current 的右子树中一直向左遍历查找
• 查找需要被删除的节点 current 的前驱时，则需要在 current 的左子树中查找最大值，即在 current 的左子树中一直向右遍历查找

//封装查找后继的方法
BinarySearchTree.prototype.getSuccessor = function (delNode) {
	// a. 定义变量,保存找到的后继
	let successor = delNode // 后继节点
	let current = delNode.right // 当前节点
	let successorParent = delNode // 后继节点的父节点

	// b. 循环查找current的右子树节点
	while (current != null) {
		successorParent = successor
		successor = current
		current = current.left
	}

	// c. 判断寻找到的后继节点是否直接就是删除节点的right节点
	if (successor != delNode.right) {
		// 后继节点的父节点的左子节点 = 后继节点的右子节点
		successorParent.left = successor.right
		// 后继节点的右子节点 = 删除节点的右子节点
		successor.right = delNode.right
	}

	// d. 返回后继节点
	return successor
}

两个节点的删除代码

// 分类3：删除的节点有两个子节点
// a 获取后继节点
let successor = this.getSuccessor(current)
// b. 判断节点类型
if (current == this.root) {
	// 如果是根节点
	this.root = successor
} else if (isLeftChild) {
	// 只有左子节点
	parent.left = successor
} else {
	// 只有右子节点
	parent.right = successor
}

// c. 将后继的左子节点改为被删除节点的左子节点
successor.left = current.left

删除完整代码

// 8. remove 方法：删除节点
BinarySearchTree.prototype.remove = function (key) {
	/* 8.1 寻找需要删除的节点*/
	// 8.1.1 定义临时保存的变量
	let current = this.root // current保存删除的节点
	let parent = null // parent保存current的父节点
	let isLeftChild = true // isLeftChild保存current是否为parent的左节点

	// 8.1.2 开始查找需要删除的节点
	while (current.key != key) {
		parent = current

		// 判断向左还是向右查找
		if (key < current.key) {
			// 小于往左查找
			isLeftChild = true
			current = current.left
		} else {
			// 大于往后查找
			isLeftChild = false
			current = current.right
		}

		// 找到最后依然没有找到相等的节点
		if (current == null) {
			return false
		}
	}
	//结束while循环后：current.key = key

	/* 8.2 据对应情况删除节点 */
	if (current.left == null || current.right == null) {
		// 分类1：删除的是叶子节点(没有子节点)
		if (current == this.root) {
			// 如果是根节点，直接置null
			this.root = null
		} else if (isLeftChild) {
			// 只有左子节点
			parent.left = null
		} else {
			// 只有右子节点
			parent.right = null
		}
	} else if (current.right == null) {
		// 分类2：删除的节点有一个子节点：当current存在左子节点时
		if (current == this.root) {
			// 如果是根节点
			this.root = current.left
		} else if (isLeftChild) {
			// 只有左子节点
			parent.left = current.left
		} else {
			// 只有右子节点
			parent.right = current.left
		}
	} else if (current.left == null) {
		// 分类2：删除的节点有一个子节点：当current存在右子节点时
		if (current == this.root) {
			// 如果是根节点
			this.root = current.right
		} else if (isLeftChild) {
			// 只有左子节点
			parent.left = current.right
		} else {
			// 只有右子节点
			parent.right = current.right
		}
	} else {
		// 分类3：删除的节点有两个子节点
		// a 获取后继节点
		let successor = this.getSuccessor(current)
		// b. 判断节点类型
		if (current == this.root) {
			// 如果是根节点
			this.root = successor
		} else if (isLeftChild) {
			// 只有左子节点
			parent.left = successor
		} else {
			// 只有右子节点
			parent.right = successor
		}

		// c. 将后继的左子节点改为被删除节点的左子节点
		successor.left = current.left
	}

	return true
}

//封装查找后继的方法
BinarySearchTree.prototype.getSuccessor = function (delNode) {
	// a. 定义变量,保存找到的后继
	let successor = delNode // 后继节点
	let current = delNode.right // 当前节点
	let successorParent = delNode // 后继节点的父节点

	// b. 循环查找current的右子树节点
	while (current != null) {
		successorParent = successor
		successor = current
		current = current.left
	}

	// c. 判断寻找到的后继节点是否直接就是删除节点的right节点
	if (successor != delNode.right) {
		// 后继节点的父节点的左子节点 = 后继节点的右子节点
		successorParent.left = successor.right
		// 后继节点的右子节点 = 删除节点的右子节点
		successor.right = delNode.right
	}

	// d. 返回后继节点
	return successor
}

测试

// 8.测试删除代码
//删除没有子节点的节点
console.log(bst.remove(3)) // true

//删除有一个子节点的节点
console.log(bst.remove(5)) // true

//删除有两个子节点的节点
console.log(bst.remove(9)) // true

//遍历二叉搜索树并输出
var resultString = ""
bst.preOrderTraversal(function (key) {
	resultString += key + " "
})
console.log(resultString) // 11 7 10 8 15 13 12 14 20 18 25

完整代码

// 创建二叉搜索树的类：BinarySearchTree
function BinarySearchTree() {
	// 节点内部类：创建节点构造函数
	function Node(key) {
		this.key = key
		this.left = null
		this.right = null
	}

	// 保存根的属性
	this.root = null

	/* 方法 */
	// 1. insert方法：插入数据，对外给用户调用的方法
	BinarySearchTree.prototype.insert = function (key) {
		// 1.1 根据key创建节点
		var newNode = new Node(key)
		// 1.2 判断根节点是否有值
		if (this.root == null) {
			// 根节点不存在，新节点作为根节点
			this.root = newNode
		} else {
			// 根节点存在，则调用内部的查找并插入节点方法
			this.insertNode(this.root, newNode)
		}
	}
	// 内部用于递归插入节点的方法：用于比较节点从左边插入还是右边插入
	BinarySearchTree.prototype.insertNode = function (node, newNode) {
		if (newNode.key < node.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)
			}
		}
	}

	// 2. preOrderTraversal 方法：先序遍历
	BinarySearchTree.prototype.preOrderTraversal = function (handler) {
		this.preOrderTraversalNode(this.root, handler)
	}
	// 封装内部方法，对某个节点进行遍历
	BinarySearchTree.prototype.preOrderTraversalNode = function (node, handler) {
		if (node != null) {
			// 2.1 处理经过的节点
			handler(node.key)

			// 2.2 递归遍历经过节点的左子树的节点
			this.preOrderTraversalNode(node.left, handler)

			// 2.3 遍历经过节点的右子树的节点
			this.preOrderTraversalNode(node.right, handler)
		}
	}

	// 3. inOrderTraversal 方法：中序遍历
	BinarySearchTree.prototype.inOrderTraversal = function (handler) {
		this.inOrderTraversalNode(this.root, handler)
	}
	// 封装内部方法，对某个节点进行遍历
	BinarySearchTree.prototype.inOrderTraversalNode = function (node, handler) {
		if (node != null) {
			// 3.1 递归遍历经过节点的左子树的节点
			this.inOrderTraversalNode(node.left, handler)

			// 3.2 处理经过的节点
			handler(node.key)

			// 3.3 遍历经过节点的右子树的节点
			this.inOrderTraversalNode(node.right, handler)
		}
	}

	// 4. postOrderTraversal 方法：后序遍历
	BinarySearchTree.prototype.postOrderTraversal = function (handler) {
		this.postOrderTraversalNode(this.root, handler)
	}
	// 封装内部方法，对某个节点进行遍历
	BinarySearchTree.prototype.postOrderTraversalNode = function (node, handler) {
		if (node != null) {
			// 4.1 递归遍历经过节点的左子树的节点
			this.postOrderTraversalNode(node.left, handler)

			// 4.2 遍历经过节点的右子树的节点
			this.postOrderTraversalNode(node.right, handler)

			// 4.3 处理经过的节点
			handler(node.key)
		}
	}

	// 5. min 方法：获取最小值
	BinarySearchTree.prototype.min = function () {
		// 5.1 获取根节点
		let node = this.root
		// 5.2 依次向左不断查找，直到左子节点为null
		while (node.left != null) {
			node = node.left
		}
		// 5.3 返回key值
		return node.key
	}

	// 6. max 方法：获取最大值
	BinarySearchTree.prototype.max = function () {
		// 6.1 获取根节点
		let node = this.root
		// 6.2 依次向右不断查找，直到右子节点为null
		while (node.right != null) {
			node = node.right
		}
		// 6.3 返回key值
		return node.key
	}

	// 7. search 方法： 搜索特定的值
	// 方式一：循环查找
	BinarySearchTree.prototype.search = function (key) {
		// 7.1 获取根节点
		let node = this.root

		// 7.2 循环搜索key
		while (node != null) {
			if (key < node.key) {
				// 小于根(父)节点就往左边找
				node = node.left
			} else if (key > node.key) {
				// 大于根(父)节点就往右边找
				node = node.right
			} else {
				// 找到就返回true
				return true
			}
		}
		// 7.3 全部没找到就返回false
		return false
	}

	// // 方式二：递归找到
	// BinarySearchTree.prototype.search = function (key) {
	// 	return this.searchNode(this.root, key)
	// }
	// BinarySearchTree.prototype.searchNode = function (node, key) {
	// 	// 1.如果传入的node为null那么, 那么就退出递归
	// 	if (node === null) {
	// 		return false
	// 	}

	// 	// 2.判断node节点的值和传入的key大小
	// 	if (node.key > key) {
	// 		// 2.1.传入的key较小, 向左边继续查找
	// 		return this.searchNode(node.left, key)
	// 	} else if (node.key < key) {
	// 		// 2.2.传入的key较大, 向右边继续查找
	// 		return this.searchNode(node.right, key)
	// 	} else {
	// 		// 2.3.相同, 说明找到了key
	// 		return true
	// 	}
	// }

	// 8. remove 方法：删除节点
	BinarySearchTree.prototype.remove = function (key) {
		/* 8.1 寻找需要删除的节点*/
		// 8.1.1 定义临时保存的变量
		let current = this.root // current保存删除的节点
		let parent = null // parent保存current的父节点
		let isLeftChild = true // isLeftChild保存current是否为parent的左节点

		// 8.1.2 开始查找需要删除的节点
		while (current.key != key) {
			parent = current

			// 判断向左还是向右查找
			if (key < current.key) {
				// 小于往左查找
				isLeftChild = true
				current = current.left
			} else {
				// 大于往后查找
				isLeftChild = false
				current = current.right
			}

			// 找到最后依然没有找到相等的节点
			if (current == null) {
				return false
			}
		}
		//结束while循环后：current.key = key

		/* 8.2 据对应情况删除节点 */
		if (current.left == null || current.right == null) {
			// 分类1：删除的是叶子节点(没有子节点)
			if (current == this.root) {
				// 如果是根节点，直接置null
				this.root = null
			} else if (isLeftChild) {
				// 只有左子节点
				parent.left = null
			} else {
				// 只有右子节点
				parent.right = null
			}
		} else if (current.right == null) {
			// 分类2：删除的节点有一个子节点：当current存在左子节点时
			if (current == this.root) {
				// 如果是根节点
				this.root = current.left
			} else if (isLeftChild) {
				// 只有左子节点
				parent.left = current.left
			} else {
				// 只有右子节点
				parent.right = current.left
			}
		} else if (current.left == null) {
			// 分类2：删除的节点有一个子节点：当current存在右子节点时
			if (current == this.root) {
				// 如果是根节点
				this.root = current.right
			} else if (isLeftChild) {
				// 只有左子节点
				parent.left = current.right
			} else {
				// 只有右子节点
				parent.right = current.right
			}
		} else {
			// 分类3：删除的节点有两个子节点
			// a 获取后继节点
			let successor = this.getSuccessor(current)
			// b. 判断节点类型
			if (current == this.root) {
				// 如果是根节点
				this.root = successor
			} else if (isLeftChild) {
				// 只有左子节点
				parent.left = successor
			} else {
				// 只有右子节点
				parent.right = successor
			}

			// c. 将后继的左子节点改为被删除节点的左子节点
			successor.left = current.left
		}

		return true
	}

	//封装查找后继的方法
	BinarySearchTree.prototype.getSuccessor = function (delNode) {
		// a. 定义变量,保存找到的后继
		let successor = delNode // 后继节点
		let current = delNode.right // 当前节点
		let successorParent = delNode // 后继节点的父节点

		// b. 循环查找current的右子树节点
		while (current != null) {
			successorParent = successor
			successor = current
			current = current.left
		}

		// c. 判断寻找到的后继节点是否直接就是删除节点的right节点
		if (successor != delNode.right) {
			// 后继节点的父节点的左子节点 = 后继节点的右子节点
			successorParent.left = successor.right
			// 后继节点的右子节点 = 删除节点的右子节点
			successor.right = delNode.right
		}

		// d. 返回后继节点
		return successor
	}
}

// 测试代码
var bst = new BinarySearchTree()

// 1. 测试插入数据
bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(3)
bst.insert(9)
bst.insert(8)
bst.insert(10)
bst.insert(13)
bst.insert(12)
bst.insert(14)
bst.insert(20)
bst.insert(18)
bst.insert(25)

bst.insert(6)
console.log(bst)

// 2. 测试前序遍历结果
var resultString = ""
bst.preOrderTraversal(function (key) {
	resultString += key + " "
})
console.log(resultString) // 11 7 5 3 6 9 8 10 15 13 12 14 20 18 25

// 3. 测试中序遍历结果
resultString = ""
bst.inOrderTraversal(function (key) {
	resultString += key + " "
})
console.log(resultString) // 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25

// 4. 测试后续遍历结果
resultString = ""
bst.postOrderTraversal(function (key) {
	resultString += key + " "
})
console.log(resultString) // 3 6 5 8 10 9 7 12 14 13 18 25 20 15 11

// 5. 获取最小值
console.log(bst.min()) // 3
// 6. 获取最大值
console.log(bst.max()) // 25

// 7. 查找特定的值
console.log(bst.search(10)) // true
console.log(bst.search(21)) // false

// 8.测试删除代码
//删除没有子节点的节点
console.log(bst.remove(3)) // true

//删除有一个子节点的节点
console.log(bst.remove(5)) // true

//删除有两个子节点的节点
console.log(bst.remove(9)) // true

//遍历二叉搜索树并输出
var resultString = ""
bst.preOrderTraversal(function (key) {
	resultString += key + " "
})
console.log(resultString) // 11 7 10 8 15 13 12 14 20 18 25

总结

二叉搜索树的优点：

• 可以快速地搜索到给定关键字的数据项
• 可以快速地插入和删除数据项

二叉搜索树的缺点：

• 当插入的数据是有顺序的时候，会造成二叉搜索树的深度过大，进而严重影响二叉搜索树的性能
• 如下图，原有二叉树 11 7 15(左图)，当插入一组有序数据：6 5 4 3 2(右图)

非平衡树

• 比较好的二叉搜索树，它的数据应该是左右均匀分布的
• 但是插入连续数据后，二叉搜索树中的数据分布就变得不均匀了，我们称这种树为非平衡树
• 对于一棵平衡二叉树来说，插入/查找等操作的效率是 O(logN)
• 而对于一棵非平衡二叉树来说，相当于编写了一个链表，查找效率变成了 O(N)

树的平衡性

• 为了能以较快的时间 O(logN)来操作一棵树，我们需要保证树总是平衡的
• 起码大部分是平衡的，此时的时间复杂度也是接近 O(logN)的
• 这就要求树中每个节点左边的子孙节点的个数，应该尽可能地等于右边的子孙节点的个数

常见的平衡树

• AVL 树：是最早的一种平衡树，它通过在每个节点多存储一个额外的数据来保持树的平衡。由于 AVL 树是平衡树，所以它的时间复杂度也是 O(logN)。但是它的整体效率不如红黑树，开发中比较少用
• 红黑树：同样通过一些特性来保持树的平衡，时间复杂度也是 O(logN)。进行插入/删除等操作时，性能优于 AVL 树，所以平衡树的应用基本都是红黑树