#

TIP

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

# 结构

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

# 术语

tree

  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

# 三种表示方法

# 普通表示法

tree

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

# 儿子-兄弟表示法

tree

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

# 儿子-兄弟旋转表示法

tree

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

# 二叉树

TIP

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

# 组成

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

# 五种形态

tree

# 特性

  • 一个二叉树的第 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 的规律

tree

# 完美二叉树

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

tree

# 完全二叉树

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

tree

# 数据存储

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

(1) 数组存储

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

tree

节点 A B C D E F G H I
序号 1 2 3 4 5 6 7 8 9
  • 非完全二叉树:需要转换成完全二叉树才能按照上面的方案存储,这样会浪费很大的存储空间

tree

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

(2) 链表存储

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

tree

# 二叉搜索树

TIP

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

# 性质

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

tree

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

# 搜索举例

tree

上图为一个二叉搜索树,若想在其中查找数据 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

图解搜索过程如下:

tree

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

# 遍历方式

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

# 常见操作

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

# 基本属性代码封装

图例说明

tree

如上图所示:二叉搜索树有四个最基本的属性:指向节点的根(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)

结果树如下:

tree

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

bst.insert(6)

新的结果树如下:

tree

# preOrderTraversal 先序遍历

遍历过程

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

tree

代码实现

// 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)
	}
}

代码解析

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

图解遍历

tree

测试结果

// 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 中序遍历

遍历过程

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

tree

代码实现

// 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)
	}
}

代码解析

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

图解遍历

tree

测试结果

// 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 后序遍历

遍历过程

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

tree

代码实现

// 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)
	}
}

代码解析

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

图解遍历

tree

测试结果

// 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
}

图解遍历

tree

测试结果

// 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

tree

// 分类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):

tree

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

tree

// 分类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 的后继

tree

代码实现思路

  • 查找需要被删除的节点 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(右图)

tree

非平衡树

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

树的平衡性

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

常见的平衡树

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